Luận văn Nghiên cứu phương pháp nhận dạng hình dạng

−ơng pháp nền: một sẽ là mong arg A phân bố đều trong [-π,π], mặc dù phân bố theo chiều dọc hoặc ngang đôi khi tập trung hơn. Phân bố của phần chính |A| đ−ợc thay thế từ một các đồng dạng, lý luận một xác suất phân bố thực tế tr−ớc cho |A| hoặc B lấy từ A. Phân bố ph−ơng pháp nền phải đ−ợc học từ cảnh và ảnh mục tiêu. Chú ý : ý t−ởng giới thiệu ở đây cũng giữ cho cluster biến đổi mối quan hệ. Cho tr−ờng hợp này θ, ϕ, Sx, Sy đ−ợc đề cập tới là độc lập với nhau. Phân bố của chúng có thể đ−ợc học từ kinh nghiệm nh− xác suất phân bố của (tx, ty) từ (θ, ϕ, Sx, Sy). Cấu trúc này, đáp ứng kinh nghiệm mặc dù không có lý thuyết nào chứng minh trực tiếp. 2.3.4.3. Kỹ thuật nhóm - 55 - Có một vài ph−ơng thức xây dựng một cây nhị phân từ tập dữ liệu và phép đo không t−ơng đồng. Trong phần này : Cây chiều dài cực tiểu đ−ợc sử dụng. Cấu trúc của nó đ−ợc sử dụng một thuật toán kết nối đơn làm việc nh− sau. Độ không t−ơng đồng nào giữa hai điểm dữ liệu đ−ợc mở rộng tới bất kỳ cặp nào cảu tập tách rời tập dữ liệu điểm A và B bằng : Một cây nhị phân đ−ợc cấu trúc bởi thủ tục lặp : mỗi dữ liệu điểm đ−ợc coi nh− là nút lá. Sau đó kết hợp cặp gần nhất của nút thành nút đơn. Lặp lại cho đến khi mọi nút đ−ợc tích hợp trong tập dữ liệu. Bằng việc thay thế min bởi max về phép tính trên, một cây chiều dài cực đại đ−ợc mô tả thay thế. Lựa chọn một cây hoặc cây còn lại có thể đ−ợc áp dụng nh−ng không có cách nào tổng quan hơn. 2.4. Thảo luận Phần này giới thiệu tổng quan việc tách và lựa chọn nhóm trong tập dữ liệu điểm. Nhóm có ý nghĩa không thể sinh ra bởi sự ngẫu nhiên. Chúng có thể đ−ợc địng nghĩa nh− độ lệch lớn từ một giả thiết độc lập của các điểm hàm chứa chúng. Điều này cho phép định nghĩa một phép đo của sự có ý nghĩa, số các cảnh báo sai( NFA). Trong tất cả các nhóm có ý nghĩa chỉ những nhóm không thể chia thành nhóm nhỏ hơn là thích hợp. Ph−ơng pháp t−ơng tự có thể dẫn tới việc lựa chọn các nhóm có ý nghĩa cực đại này. Ph−ơng pháp này phụ thuộc vào các b−ớc cluster mà cluster lại phụ thuộc rất nhiều vào ng−ời sử dụng và tính toán NFAg phải thích nghi với các nhóm phát sinh. Ph−ơng thức sử dụng để tìm ra đặc tính thực sự liên quan tới dạng nhóm trực quan trong tập đối t−ợng. Làm thế nào để lựa chọn đặc tính để mô tả nhóm có ý nghĩa và ở đây thủ tục cluster đ−ợc đề cập là phép phân tích vận động trực quanvà giới thiệu tách trong không gian thời gian t−ơng ứng. - 56 - Ch−ơng 3 Ph−ơng pháp ra quyết định Contrario Nhận dạng hình dạng là nhận biết ra hình dạng dựa trên các kiến thức biết tr−ớc, cụ thể ở đây là tìm ra có hay không hình dạng truy vấn trong CSDL hình dạng. Phần lớn các ph−ơng pháp nhận dạng dựa trên phép đo t−ơng đồng hoặc không t−ơng đồng. Quyết định cuối cùng trả lời rõ ràng có hay không hai hình dạng giống nhau. Phần này đ−a ra giải pháp nhận dạng chủ yếu dựa vào giới hạn số cảnh báo sai(NFA) của truy vấn hình dạng trong số hình dạng trong CSDL. Ph−ơng pháp ra quyết định với ít tham số hơn để quyết định có hay không hai ảnh bất kỳ chia sẻ một số hình dạng. Biểu diễn hình dạng đ−ợc đề cập với nguyên tắc là sự nhận biết. Xác định t−ơng ứng giữa các nhân tố hình dạng không chỉ là định nghĩa một khái niệm sự t−ơng đồng giữa chúng, nh−ng cũng có thể quyết định có hay không 2 thành phần hình dạng là một cặp. Phần này giới thiệu luật ra quyết định tự động, áp dụng ph−ơng pháp này để đối sánh hình dạng và mở rộng phạm vi của ph−ơng pháp so với lý thuyết. Đặc biệt, ý nghĩa luật tự động ra quyết định với đối sánh hình dạng trong một CSDL mà có thể dựa vào khoảng cách giữa các hình dạng. Từ hai hình dạng và một khoảng cách δ rất nhỏ giữa chúng có hai khả năng: 1- Cả hai hình dạng ở cùng một khoảng cách khi đối sánh 2- CSDL hình dạng đ−ợc trích chọn quá lớn, phải thay đổi một trong số những hình dạng này kết thúc S (Giữa chúng không có đối t−ợng giống nhau) - 57 - Giả thiết, mỗi δ có thể −ớc l−ợng, xác suất xảy ra khả năng thứ hai. Nếu số l−ợng này xảy ra rất nhỏ đối với hai hình dạng thì khả năng thứ nhất đ−ợc giải thích tốt hơn. Ph−ơng pháp này gọi là quyết định Contrario. Trong hệ thống quan sát tính toán, sự thử đầu tiên để có khả năng tách trong một ảnh Contrario tới một không gian tuần tự từ phân tích trực quan của David Lowe. Các đối t−ợng tìm kiếm đ−ợc mã hóa bằng h−ớng biên và so sánh bằng cách sử dụng một quan hệ khoảng cách Hausdory. Đ−a ra −ớc l−ợng xác xuất xuất hiện cảnh báo sai của bản thân ảnh; sử dụng xác suất này để ra một quyết định. Một ph−ơng pháp sử dụng −ớc l−ợng để thiết lập ng−ỡng đối sánh mỗi một xác suất của một cảnh báo sai d−ới mức của một vài xác suất xác định tr−ớc. Tuy nhiên, vấn đề trong khi Cluster ảnh đúng hay sai có thể có nguyên nhân từ ng−ỡng đã thiết lập. Grimson và Hutten giới thiệu ng−ỡng cố định trên tỷ lệ của các ph−ơng thức đặc tr−ng : “ Biên trong số đặc tr−ng của ảnh ( đề cập tới biến đổi không gian ) dựa trên việc tách chính xác. Chấp nhận phần lớn các đặc tr−ng phân bố đồng đều( ph−ơng pháp nền ), để hạn chế tính ngẫu nhiên thuật ngữ nàyphải định nghĩa. Ph−ơng pháp tính toán dựa vào một số giả thiết hạn chế( ph−ơng pháp hình dạng có sẵn; các đặc tr−ng phân bố đồng đều). Những giới hạn này là khó khăn cho từng tr−ờng hợp thực tế. Ví dụ trong ảnh y tế của não bộ, các điểm không phân bố đều trên ảnh nh−ng không quá ngẫu nhiên trên bề mặt vỏ não và sọ não. Mở rộng sẽ tính toán xác suất sai xác thực trực tuyến trong khi nhận dạng. Việc này cho phép chúng ta thống kê lại xác xuất phân bố đặc biệt của ph−ơng thức và đặc tr−ng cảnh. Đây là mục tiêu hoàn toàn chính xác. Ph−ơng pháp xác suất đáng tin cậy cho vấn đề hình dạng t−ơng ứng và đ−a ra một ph−ơng pháp để tính toán tự động mức ng−ỡng đối sánh đúng. Thay vì định nghĩa khoảng cách ng−ỡng cho mỗi truy vấn hình dạng, định nghĩa số cảnh báo sai NFA, có thể là ng−ỡng độc lập với truy vấn hình dạng. NFA có thể đ−ợc - 58 - giải thích nh− một số mong muốn các hình dạng ngẫu nhiên tại một vài khoảng cách từ một truy vấn hình dạng, thậm chí ng−ỡng NFA dẫn tới ng−ỡng đối sánh khoảng cách, chỉ ra khi thêm một thông tin vào đối sánh sự t−ơng đồng ta sẽ có đối sánh đúng đến mức nào. Đối sánh sẽ khắc phục vấn đề tổng quát của quyết định có hay không hai nhân tố hình dạng đ−ợc biểu diễn bởi một mã quan hệ không có sự giống nhau bất biến. Phần này giới thiệu khái niệm đối sánh có ý nghĩa, nó có thể sắp xếp các đối sánh với một nhân tố hình dạng chuẩn hoá với một ý nghĩa chính xác và thuận tiện: số các cảnh báo sai( NFA). Tuy nhiên, ng−ợc lại với phần lớn ph−ơng pháp đang có, không chỉ NFA mà ta có thể sắp xếp thứ tự các đối sánh từ thấp đến cao, nh−ng ng−ỡng tách thích hợp với truy vấn hình dạng và cơ sở dữ liệu cùng thu đ−ợc từ đ−ờng viền đồng dạng dựa trên NFA. Ph−ơng pháp quyết định trích chọn đ−ờng viền đ−ợc giới thiệu dựa trên việc chuẩn hoá cung tròn, nhân tố hình dạng đ−ợc trích chọn từ ảnh, rồi tính toán đối sánh và sau đó ra quyết định. 3.1. Một quyết định Contrario ở đây fix cứng mức ng−ỡng để chấp nhận hay loại bỏ ng−ỡng nhận dạng nhân tố hình dạng, tiến tới một phân lớp cố định. Mỗi nhân tố hình dạng đ−ợc mô tả bởi một mã( một danh sách các đặc tr−ng bất biến của một vài không gian đặc tr−ng). Nhận dạng là vấn đề khó: từ cách lựa chọn nhân tố hình dạng theo một phép đo t−ơng đ−ơng, một truy vấn nhân tố hình dạng phải trả lời câu hỏi “ có hay không có nhân tố hình dạng giống nh− nhân tố hình dạng truy vấn, trong tr−ờng hợp đó, cốt yếu ở tự động thiết lập ng−ỡng δ trên phép đo t−ơng đ−ơng và đem lại một mức thích hợp để ra quyết định. Đây là mục tiêu của ph−ơng pháp này. Xây dụng một ph−ơng pháp thống kê của CSDL nhân tố hình dạng và các đối sánh quan hệ đ−ợc tách Contrario. 3.1.1. Ph−ơng pháp hình dạng trái ng−ợc ph−ơng pháp nền - 59 - Đầu tiên phải định nghĩa chính xác biểu diễn nhân tố hình dạng và một vài khái niệm khác. Mục tiêu của ph−ơng pháp là so sánh truy vấn nhân tố hình dạng S với nhân tố hình dạng N của CSDL B. Giả thiết mỗi nhân tố hình dạng S đ−ợc biểu diễn bởi tập K đặc tr−ng X1(S), X2(S), …. , Xk(S) ; mỗi nhân tố hình dạng đều thuộc một không gian đo ( Ei , di ) i ∈ {1, … , k }. Định nghĩa khoảng cách giữa các nhân tố hình dạng nh− khoảng cách : E1 x E2 x … x Ek d( S , S’ ) = max di( xi(S), xi(S’) ) i = {1 … k} Một CSDL hình dạng S đ−ợc quan sát hoặc khoảng cách d(S,S’) chính xác hơn giữa hai truy vấn đ−ợc quan sát. Vấn đề là khoảng cách d(S,S’) có đủ nhỏ để ra quyết định cặp S,S’ tạo thành cảnh hay khoảng cách d(S,S’) quá lớn nên chúng không thể tạo thành bất cứ cảnh nào. Định nghĩa 3.1 : gọi ph−ơng pháp nền, bất kỳ ph−ơng pháp ngẫu nhiên (Ω, A, Pr ), mỗi tham số phụ thuộc công thức sau : đ−ợc tính toán độc lập, chú ý bởi Pi( S, δ ), Tỉ số theo kinh nghiệm: ở đây, # tập hữu hạn và N là các nhân tố hình dạngthuộc CSDL B, nh− một sự −ớc l−ợng của Pi( S, δ ) cho mỗi giá trịδ .Sử dụng trong thực tế Pi( S, δ ) = N 1 , # { S’∈B, di( xi(S), xi(S’) ) ≤ 0} 3.1.2. Ph−ơng thức quyết định Contrario Hàm khoảng cách giữa các nhân tố hình dạng, quyết định có hay không một đối sánh nhân tố hình dạng này với nhân tố hình dạng khác dựa vào tập mức - 60 - ng−ỡng khoảng cách δ . δ đ−ợc thiết lập tự động. Tìm cách thay thế giới hạn khoảng cách bằng giới hạn xác suất của cách báo sai. Một hình dạng S’ đ−ợc quan sát, lý thuyết: H0: “ S’ đ−ợc sinh ra từ ph−ơng thức của S “. Tuy nhiên, vận dụng lý thuyết này với sự thừa nhận( không một ph−ơng thức hình dạng nào có sẵn cho S ) là dễ dàng. Vì vậy dẫn tới tập trung thay đổi lý thuyết xen kẽ H1 :“ S’ đ−ợc phát sinh từ ph−ơng thức nền ”. Cho mỗi δ ; “tập nhân tố hình dạng đ−ợc chia thành hai tập con Ω0(δ), Ω1(δ)”, quan hệ từ nhân tố hình dạng với khoảng cách của chúng tới S thấp hơn δ thì lý thuyết H0 đ−ợc chấp nhận và khoảng cách S >δ (H0 bị từ chối). Định nghĩa 3.2: truy vấn nhân tố hình dạng S đ−a tới tập thử Tδ(S) đ−ợc định nghĩa nh− sau: - Nếu 1 tập CSDL nhân tố hình dạng S’ có d(S,S’)< δ thì lý thuyết H0 đ−ợc chấp nhận (S’ gần với S bởi 1 vài quan hệ) tr−ờng hợp này S’ đ−ợc phân lớp vào Ω0(δ) - Còn lại H0 bị loại trừ và thay đổi lý thuyết H1 đ−ợc chấp nhận(S’ gần S). Tr−ờng hợp này S’ đ−ợc phân lớp vào lớp Ω1(δ) Đặc tính của các phép thử thống kê là phép đo bởi xác suất quyết định sai, có thể có 2 loại lỗi, lỗi thứ nhất: loại bỏ H0 cho một quan sát S, H0 lại là có thực (dạng lỗi tách sai) và loại lỗi thứ hai: chấp nhận H0 cho S mặc dù H0 là sai (lỗi sai vị trí),vậy phép đo xác suất lỗi xác địng nh− sau: - Xác suất không tách hoặc 1 lỗi(liên quan loại lỗi 1) là: - Xác suất cảnh báo sai( liên quan loại lỗi 2) , là gần đúng lớn nhất của H0 t−ơng ứng H1 trên Ω. Rõ ràng là thấp hơn α và α’, phép thử tốt hơn α và α’ không thể đánh giá độc lập. Vấn đề để tìm ra sự thoả hiệp giữa 2 xác suất này. Mở rộng sử dụng kỹ thuật cho việc tìm tỷ lệ phép thử gần đúng nhất và phép thử Bayes. Tuy nhiên, lý thuyết là có giới - 61 - hạn. Việc gần đúng của lý thuyết H0 và H1 là khó thực hiện nếu mục tiêu nhận dạng là 1 truy vấn hình dạng xác định rõ( ph−ơng pháp chung thực sự cần thiết truy vấn hình dạng S để tính toán gần đúng 1 hình dạng S’ d−ới lý thuyết H0). Tuy nhiên, lý thuyết này cần các thông tin biết tr−ớc, còn các thông tin khác có thể bổ xung sau. 3.1.3. Ước l−ợng xác suất cảnh báo sai Tóm lại không thể tính toán xác suất của việc không tách Pr(Ω1(δ)/H0). Tính toán cung cấp giá trị xác suất cảnh báo sai của phép thử thống kê Tδ(S) chú ý PFA(S, δ)= Pr(Ω1(δ)/H1) từ S’∈ Ω0(δ) nếu d(S,S’) ≤δ nó phụ thuộc công thức sau: Định nghĩa: vì vậy: Tính toán lại ta có: Proposition 3.1: Xác suất cảnh báo sai cho phép thử thống kê Tδ(S) là : Đặt lại, theo kinh nghiệm sẽ sử dụng −ớc l−ợng cho Pi(S, δ) với i∈{1, k} 3.1.4. Luật ra quyết định Contrario B−ớc tiếp theo, để giới hạn PFA, xác suất cảnh báo sai PFA(S, δ) không suy giảm với δ, muốn giảm giới hạn của xác suất cảnh báo sai PFA phải bằng cách gia tăng khoảng cách δ* : - 62 - Do vậy nếu phép thử chấp nhận lý thuyết H0, nếu khoảng cách quan sát nhỏ hơn δ*(p) và để loại trừ lý thuyết bằng nhau, kết hợp xác suất cảnh báo sai đ−ợc giới hạn bởi p, luật này gọi là quyết định Contrario. PFA kết hợp với phép thử thống kê rất thấp vì vậy thay đổi nó là không hợp lý. ứng dụng cho nhận dạng hình dạng, chấp nhận lý thuyết 1 tập nhân tố hình dạng S’ t−ơng ứng với truy vấn hình dạng đối sánh S coi nh− S’ gần S. Chú ý, đối sánh nhân tố hình dạng giống nhau nh−ng không hẳn t−ơng ứng với các đối t−ợng nh− nhau. 3.2. Tự động thiết lập ng−ỡng khoảng cách 3.2.1. Số các cảnh báo sai NFA Quyết định contrario đ−ợc giới thiệu cốt yếu là cố định mức ng−ỡng của xác suất cảnh báo sai hơn là khoảng cách giữa các nhân tố hình dạng. Từ một xác suất ít ý nghĩa, giới thiệu số cảnh báo sai cùng độ chính xác đó, trong đó truy vấn nhân tố hình dạng đ−ợc so sánh với nhân tố hình dạng từ một tập CSDL kích th−ớc N. Định nghĩa 3.3 : số các cảnh báo sai của nhân tố hình dạng S tại khoảng cách d là : Từ kết quả cuối cùng của xác suất là xác suất cảnh báo sai khi thực hiện phép thử, nếu CSDL nhân tố hình dạng tại một khoảng cách( thấp hơn d) số các cảnh báo sai có thể thấy nh− trị trung bình số cảnh báo sai đ−ợc mong đợi khi thử, quyết định có hay không khoảng cách từ mỗi nhân tố hình dạng trong CSDL S là nhỏ hơn d. Chú ý: từ mỗi Pi là −ớc l−ợng theo kinh nghiệm trên tập CSDL B ; (NFA phụ thuộc B ). - 63 - Định nghĩa 3.4: số cảnh báo sai của truy vấn nhân tố hình dạng S là số cảnh báo sai của S tại một khoảng cách d(S, S’ ). Số các cảnh báo sai giữa S và S’, t−ơng ứng sự mong đợi của CSDL hình dạng nó là các cảnh báo sai và khoảng cách của nó tới S thấp hơn d(S,S’ ). Chú ý: chú thích t−ơng tự đ−ợc sử dụng cho cả dự đoán định nghĩa số các cách báo sai, cùng chú ý argument của NFA cuối cùng. 3.2.2. Đối sánh có ý nghĩa Thay vì giới hạn trực tiếp xác suất cảnh báo sai để giảm ng−ỡng khoảng cách nh− đã giải thích, giới hạn số các cảnh báo sai NFA giải thích cho tần suất xuất hiện nh− mong đợi. Định nghĩa 3.5: Nhân tố hình dạng S’ là một đối sánh có ý nghĩa ε của truy vấn nhân tố hình dạng S nếu số các cảnh báo sai của chúng đ−ợc giới hạn bởi ε: NFA(S,S’)≤ ε Chú ý từ hàm, không suy giảm, hàm có thể đảo ng−ợc chú ý tới khoảng cách d. Tồn tại một số thực xác định duy nhất δ*(ε/N) cũng phụ thuộc vào truy vấn hình dạng S: Tiên đề 3.2: 1 nhân tố hình dạng S’ là đối sánh có ý nghĩa ε của truy vấn nhân tố hình dạng t−ơng đ−ơng: d(S,S’)≤ δ*(ε/N) Đối sánh có ý nghĩa ε của S là các nhân tố hình dạng cho khoảng cách δ* < (ε/N). Xác suất cảnh báo sai của các phép thử lần l−ợt nhỏ hơn ε/N. Mặc dù, trị trung bình cảnh báo sai nhỏ hơn ε trong số tất cả các đối sánh có ý nghĩa ε trên N nhân tố hình dạng đ−ợc thử. Ph−ơng thức này không thể −ớc l−ợng số đối sánh có - 64 - ý nghĩa ε. Tuy nhiên, nếu mọi nhân tố hình dạng trong tập CSDL đ−ợc xuất phát bởi ph−ơng pháp nền, lý thuyết H0 không bao giờ đ−ợc chấp nhận và tách có ý nghĩa ε vì vậy sẽ đ−ợc đề cập nh− cảnh báo sai. Proposition 3.3: giả thiết CSDL nhân tố hình dạng chỉ rõ phân bố theo ph−ơng pháp nền; dự báo của số các đối sánh có ý nghĩa ε < ε. Đặt S’j=(1≤j≤N) chú ý nhân tố hình dạng trong tập CSDLvà χj là hàm của thành phần ej ( S’j là đối sánh của truy vấn S (giá trị của nó là 1 nếu S’j thực sự là đối sánh có ý nghĩa ε của S và là 0 với các giá trị khác). Đặt ∑ = = N j jR 1 χ là không gian biểu diễn hình dạng có ý nghĩa ε t−ơng ứng với S. Dự đoán của R là ( ) ( )∑ = = N j jERE 1 χ sử dụng tiên đề 3.2: Từ các nhân tố hình dạng trong CSDL đ−ợc giả thiết thỏa mãn giả thiết ph−ơng pháp nền: Tính tuyến tính của dự đoán t−ơng đ−ơng biểu thức: Bằng định nghĩa δ* có ( ) ∑ = −≤ N j NRE 1 1.ε vì vậy ( ) ε≤RE Điểm mấu chốt này là tính tuyến tính của dự đoán cho phép tính toán E(R). Từ sự phụ thuộc giữa các thành phần ej không đ−ợc biết, ta có thể −ớc l−ợng luật phân bố xác suất của R. 3.2.3. Ng−ỡng nhận dạng t−ơng ứng với ngữ cảnh Chú ý rằng xác suất thử nghiệm đem vào tính toán sự ngẫu nhiên hoặc tính phổ thông của đối sánh có thể: ng−ỡng δ* là hạn chế hơn trong tr−ờng hợp đầu tiên và khắt khe hơn trong các tr−ờng hợp khác. Nếu truy vấn hình dạng S1 hơn - 65 - một truy vấn S2 khác; CSDL hàm chứa nhiều hình dạng kết thúc S2 hơn S1, nhỏ hơn khoảng cách cố định d’ nào đó. Nếu truy vấn hình dạng S1 hiếm hơn S2 ta có : i∈{1, k} vad d < d’: Hiệu suất này *1 * 2 ss δδ ≤ ( cung cấp cả hai số l−ợng nhỏ hơn d’). Càng hiếm các hình dạng tìm kiếm thì ng−ỡng nhận dạng càng cao. Phép tính toán khác của giới hạn t−ơng tự nh−: nếu đem lại một truy vấn hình dạng trong số các hình dạng của CSDL B1 hiếm hơn là CSDL dạng cao hơn B2. Có i∈{1, k} và d đủ nhỏ: ở đây 1iP , 2 iP là −ớc l−ợng riêng trên B1 và B2, ( ) ( )SS *1*2 δδ ≤ . Kết quả là ng−ỡng đ−ợc giới thiệu bởi thuật toán tự động thích nghi liên quan đến sự biến thiên của truy vấn hình dạng trong CSDL hình dạng. Càng hiếm truy vấn hình dạng thì ng−ỡng khoảng cách t−ơng ứng càng tùy ý hơn và ng−ợc lại. 3.2.4. Tại sao quyết định Contrario Tiến bộ của quyết định Contrario dựa trên NFA đ−ợc so sánh với tập các ng−ỡng khoảng cách trực tiếp giữa các nhân tố hình dạng một cách rõ ràng. Ng−ỡng NFA là khá thuận lợi so với ng−ỡng khoảng cách. Thực vậy, đơn giản đặt ε = 1 và cho phép tại phần lớn cảnh báo sai trong các đối sánh có ý nghĩa hoặc ε = 10-1 nếu ta muốn lạm dụng sự tin cậy cao hơn trong đối sánh thu đ−ợc. Ng−ỡng tách ε đ−ợc đặt t−ơng đ−ơng dù truy vấn hình dạng là nh− thế nào và CSDL có thể là kết quả khoảng cách thích nghi tự động phụ thuộc vào chúng theo giải thích ở trên. Nói cách khác, ε thấp hơn, chắc chắn tách có ý nghĩa hơn. Tuy nhiên tính toán NFA không cần thiết cho bất cứ ph−ơng pháp hình dạng nào. Nó là tiến bộ chính của ph−ơng pháp giới thiệu, có một ph−ơng pháp - 66 - hình dạng có nghĩa là truy vấn hình dạng để nhận ra tr−ớc khi dùng cách này hay cách khác. Kết thúc với định nghĩa số cảnh báo sai khi so sánh mọi hình dạng trong CSDL với mọi hình dạng khác trong CSDL và không chỉ nhân tố hình dạng trong một CSDL. Điều này t−ơng ứng với thử nghiệm ở mục sau. Hai nội dung hình dạng của hai ảnh đ−ợc đối sánh. Khi tìm kiếm hình dạng phụ thuộc CSDL B1 tạo ra hình dạng N1; trong số các nhân tố hình dạng N2 phụ thuộc CSDL B2. Định nghĩa 3.6: Số các cảnh báo sai của một hình dạng tại khoảng cách d: ( ) ( )( ) ( ) ( )( )dkiSxSxdSNNdSNFA iii ≤∈ìì= ,1,',max,Pr, '21 Xác suất (phụ thuộc vào hình dạng S đ−ợc tìm kiếm) đ−ợc −ớc l−ợng nh− tr−ớc, nh− kết quả của K −ớc l−ợng thử nghiệm trên tập B2 trong số các truy vấn hình dạng đ−ợc tìm cho mỗi hình dạng trong B1, định nghĩa đối sánh có ý nghĩa ε. Mục tiêu, trị trung bình các cảnh báo sai ε trong số đối sánh có ý nghĩa trên N1, N2 cặp đ−ợc thử không thay đổi. 3.3. Xây dựng đặc tr−ng độc lập thống kê Khá quan trọng khi đề cập đặc tr−ng độc lập (cf(A)). Khi sử dụng đặc tr−ng độc lập là một cách để giảm kích th−ớc của CSDL. Bằng sự kết hợp một vài đặc tr−ng độc lập, có thể dễ dàng tìm số cảch báo sai rất thấp mà không cần CSDL lớn để −ớc l−ợng xác suất cảnh báo sai PFA. D Lowe giới thiệu tổng quan cho nhận dạng trực quan” bởi giới hạn sự chính xác của phép đo ảnh( và xác suất cũng thiếu các đoạn quan hệ trong thế giới tự nhiên)” Mối quan hệ đơn giản đ−ợc mô tả th−ờng bị lỗi so với mức xác suất xuất hiện ngẫu nhiên rất thấp, mối quan hệ này phải đủ mạnh để nhận dạng. Tuy nhiên, những kết quả hữu ích có thể gia tăng nh− kết quả tìm kiếm hỗn hợp tạo thành các quan hệ hỗn hợp mới, nó phải có xác suất xuất hiện mới thấp hơn. Xem xét một ví dụ bằng số. Nếu đề cập tới CSDL đ−ợc tạo ra từ N nhân tố hình dạng giá trị thấp nhất có thể tìm thấy bằng xác suất theo kinh nghiệm:# - 67 - ( ) ( ) ( )( ){ }dSxSx N dSP iii ≤∈ì= ,'1, id,S'# β Tại giá trị thấp nhất 1/N. Nếu ph−ơng pháp nền xây dựng trên k =1 đặc tr−ng và CSDL N =1000 hình dạng. Giá trị thấp nhất có thể tìm thấy số cảnh báo sai là 1000.1/1000=1. Điều này có nghĩa nếu hai nhân tố hình dạng S và S’ d−ờng nh− đ−ợc định dạng dựa trên NFA ta có thể chắc chắn đối sánh này không ngẫu nhiên. Thực vậy NFA =1 có nghĩa trị trung bình 1 hình dạng trong CSDL có thể đối sánh với S bằng sự thay đổi. Giả thiết ph−ơng pháp nền đ−ợc xây dựng trên 6 đặc tr−ng (N=1000) Số cảnh báo sai thấp nhất đ−ợc tìm thấy 1000.1/10006=10-15 Trong thực tế, quan sát số các cảnh báo sai giữa hai hình dạng t−ơng đ−ơng có thể thấp hơn 10-10. Điều này có nghĩa cần quan sát 1 trong CSDL 1010 không lớn hơn để đối sánh có ý nghĩa tại khoảng cách t−ơng tự là cảnh báo sai. Để tổng hợp, các khung của chúng ta để nhận dạng hình dạng, đặc tr−ng hình dạng đặt ra 3 yêu cầu sau: 1- Các đặc tr−ng hình dạng cung cấp mô tả hoàn thiện: 2 hình dạng với các đặc tr−ng t−ơng tự đ−ợc nhận dạng. 2- Các hình dạng độc lập thống kê (khá chính xác, khoảng cách giữa hai hình dạng là độc lập). 3- Số l−ợng các hình dạng lớn. Yêu cầu thứ nhất có nghĩa là mô tả đặc tr−ng hình dạng tốt. Yêu cầu thứ hai cơ sở cho thiết kế ph−ơng pháp nền và yêu cầu thứ ba cần thiết để tìm kiếm hình dạng với số cảnh báo sai thấp. Tìm các đặc tr−ng rất khó hội tụ cả ba yêu cầu. Thực vậy phải có đủ đặc tr−ng để yêu cầu thứ nhất có giá trị nh−ng yêu cầu thứ 2 có thể bị lỗi. Khung quyết định, phải mô tả khá xa so với thực tế nói chung. Phải ứng dụng để tìm ra sự t−ơng đồng giữa bất kỳ loại cấu trúc nào trong cảnh, với k đặc tr−ng độc lập thống kê có thể đ−ợc trích chọn trong phần tiếp theo, đề cập vấn đề - 68 - trích chọn đặc tr−ng độc lập từ đoạn cung Jordan (nhân tố hình dạng). Nhân tố hình dạng đ−ợc chuẩn hóa tr−ớc khi đối sánh để yêu cầu nhận dạng hình học cố định. Vì vậy nhân tố hình dạng phải đ−ợc chuẩn hóa và trích chọn đặc tr−ng độc lập thống kê từ các nhân tố hình dạng đã đ−ợc chuẩn hoá nhằm đáp ứng ba yêu cầu này. 3.4.Chuẩn hóa nhân tố hình dạng từ ảnh cho đặc tr−ng độc lập 3.4.1. Biểu diễn hình dạng bằng các mức đ−ờng Các thử nghiệm ph−ơng pháp ra quyết định đ−ợc sử dụng trong hệ thống nhận dạng thực nh− thế nào. Một thuật toán trích chọn đoạn cung Jordan t−ơng ứng với biểu diễn hình dạng cục bộ không đổi trong ảnh đ−ợc giới thiệu tiến hành theo các b−ớc sau: 1- Trích chọn mức đ−ờng có ý nghĩa 2- Làm mịn các mối quan hệ không đổi của mức đ−ờng đ−ợc trích chọn 3- Mã hóa cục bộ đoạn mức đ−ờng sau khi chuẩn hóa các mối quan hệ t−ơng đồng. Chi tiết hơn, đề cập tới tập các mức đ−ờng trong ảnh (đ−ờng viền của các thành phần). Sự biểu diễn này có một số tiến bộ, mặc dù nó không cố định ở một vài sự thay đổi độ chói của cảnh ( Trong tr−ờng hợp này các ảnh tự nó thay đổi). Chú ý,mức đ−ờng không đổi khi thay đổi độ t−ơng phản. Đảm bảo việc học chính xác các thông tin hình dạng yêu cầu đ−ợc biểu diễn ở mức đ−ờng. Tuy nhiên, đ−ờng viền đối t−ợng nằm trong ảnh đ−ợc biểu diễn bởi tổ hợp một số đoạn các mức đ−ờng. Vì vậy, các mức đ−ờng có thể đ−ợc quan sát nh− một dãy các đoạn đ−ờng viền đối t−ợng, vì vậy phải mã hóa mọi thông tin hình dạng. Tuy nhiên, biểu diễn hình dạng bằng mức đ−ờng là không cần thiết và cũng có thể chứa thông tin vô ích. Đó là tại sao, Desolneux giới thiệu ph−ơng pháp để trích chọn mức đ−ờng có ý nghĩa từ ảnh, điều này đ−ợc hoàn thiện bởi Cao. - 69 - Qua thực nghiệm, những đ−ờng này cung cấp để trùng khớp cục bộ với đ−ờng viền trực quan của đối t−ợng trong ảnh. Thuật toán không cần sự điều chỉnh tham số, từ các tham số tự động thiết lập dựa trên số liệu thống kê thu đ−ợc từ nguyên tắc trực quan. Mức đ−ờng có ý nghĩa là độ t−ơng phản không đổi, từ các phát hiện của chúng dựa trên phân bố sự t−ơng phản của ảnh. Hình 3.1 minh họa việc mất thông tin, có nghĩa là bằng việc sử dụng mức đ−ờng có ý nghĩa đ−ợc so sánh với tăng độ chính xác của thông tin. Sự giảm bớt các mức đ−ờng nhằm mục đích đối sánh hình dạng sau mã hóa. Mặt khác, ngăn chặn yếu tố ph−ơng pháp không đ−ợc ứng dụng của, Ví dụ nh− tìm kiếm ảnh từ CSDL. Từ một mức đ−ờng có ý nghĩa đ−ợc trích chọn, cần làm nhẵn chúng để hạn chế nhiễu và ảnh h−ởng của nhiễu. Không gian độ chia quan hệ hình học (Geometric Affine) phải thích hợp (từ mỗi sự làm nhẵn thay thế với biến đổi quan hệ riêng và từ đó quan tâm tới quan hệ không đổi: ở đây x là điểm trên mức đ−ờng, Curv(x) là độ cong và n (x) th−ờng là độ cong, h−ớng về phía lõm, sử dụng thực hiện nhanh bởi Moisan. Độ chia tại điểm làm nhẵn đ−ợc ứng dụng để cố định kích th−ớc pixel. Fix cứng độ chia tại điểm làm nhẵn để mở rộng chi tiết của hình dạng ảnh ở điểm trên cung đ−ợc trích chọn. Mục đích là giảm bớt sự phức tạp của các mức đ−ờng có ý nghĩa hoàn thiện bằng cách chuẩn hoá chúng. Mục tiêu còn lại cũng nhằm mục đích tạo các đối sánh hình dạng chắc chắn. Thực vậy, làm mịn là hạn chế số đ−ờng mảnh bitangents (màu sẫm) trên mức đ−ờng để hạn chế các nhiễu; kết quả tất nhiên nó cũng hạn chế số nhân tố hình dạng đ−ợc mã hóa và nh− vậy mức đ−ờng sẽ trở lên rõ ràng hơn. Cuối cùng, thuật toán mã hóa hình dạng không đổi thực hiện chuẩn hóa cục bộ và mã hóa. Để xây dựng biểu diễn không đổi ( biến đổi quan hệ hoặc - 70 - t−ơng đồng), định nghĩa khung cục bộ cho mỗi mức đ−ờng, dựa trên h−ớng mạnh lên (robust, chú ý đ−ờng sẫm tại đoạn béo, hoặc đ−ờng mảnh). Mỗi biểu diễn thu đ−ợc bằng lấy mẫu đồng dạng một đoạn đ−ờng cong trong khung tiêu chuẩn hóa này. Sự liên kết của ba sự xắp xếp này đ−ợc giới thiệu đầu tiên bởi Lisani. Cách thứ ba dụa trên bài báo của Lamdan cho phép công việc của Reths trên đánh chỉ mục không đổi và gần đây hơn là Orrite. Phần sau giới thiệu thuật toán cải tiến của Lisani. Hình 3.1: trích chọn mức đ−ờng có ý nghĩa a-ảnh gốc “ La Conpouaille “. b-Mức đ−ợc giới thiệu biểu diễn với chất l−ợng mức xám cao từng b−ớc t−ơng ứng 10 (54 790 mức đ−ờng). Mức đ−ờng có ý nghĩa M’ (296 detetion). 3.4.2.Tiêu chuẩn hóa và mã hóa bán cục bộ Giới thiệu tiêu chuẩn hóa mức đ−ờng bán cục bộ, tổng quan hơnchính là cung Jordan dựa trên h−ớng cực đại. Việc tách này đ−ợc cung cấp bằng đ−ờng mảnh hoặc đ−ờng đậm tại đoạn nhẵn. (Một đoạn là vế trái của cung không tiến tới phân đoạn điểm điểm, mối quan hệ với ph−ơng pháp nền. Trong khi đ−ờng mảnh là một khả năng quan hệ không đổi; nó không phải là đoạn bằng phẳng. Tuy nhiên, hai đối số cho sự đề cập của nó; đầu tiên, d−ới lý do nhân tố zoom, đoạn bằng phẳng đ−ợc duy trì, lý do thứ hai là điểm cong, tất yếu cũng đ−ợc duy trì bởi biến đổi quan hệ. Nếu không phải tr−ờng hợp này, tại điểm cong sẽ không - 71 - phải là h−ớng mạnh. Trong cảnh, điểm đậm tại đoạn bằng phẳng có thể đ−ợc đề cập nh− version mạnh của độ đậm tại điểm cong (sử dụng thuật toán gốc của Lisani ) cùng với đ−ờng mảnh và version không mạnh của phần bằng phẳng. Chi tiết thủ tục sử dụng để thực hiện t−ơng tự và mối quan hệ không đổi cho mã hóa / tiêu chuẩn hóa cục bộ đ−ờng cong Jordan. Tiếp theo, đề cập trực tiếp tham số Euclidean cho mức đ−ờng. 3.4.2.1. Mã hóa / Tiêu chuẩn hóa trị không đổi t−ơng đ−ơng Chi tiết ở hình 3.2, hai tham số thực hiện, F và N bao gồm trong thủ tục tiêu chuẩn hóa này. Giá trị của F xác định chiều dài chuẩn hóa của nhân tố hình dạng, và nó đ−ợc lựa chọn: nếu F quá lớn, nhân tố hình dạng sẽ không đ−ợc chấp nhận tốt với thực tế, trong khi nếu F quá nhỏ nhân tố hình dạng không đủ để phân biệt. Mặt khác, một vấn đề cơ bản trong phân tích hình dạng: tính cục bộ trái ng−ợc với tính chung trong biểu diễn hình dạng. Từ t−ơng quan biểu diễn hình dạng thì việc lựa chọn N ít khó khăn hơn, vì vậy các tham số t−ơng đối chính xác. Giá trị của nó đ−ợc lựa chọn nh− một sự thỏa thuận giữa biểu diễn hình dạng chính xác với việc đảm bảo tính toán nhanh. Hình 3.3 : Chỉ ra một vài tiêu chuẩn hình dạng đ−ợc trích chọn từ đ−ờng đơn. Nhiệm vụ tính toán với F=5 và N=45. Chú ý : Biểu diễn có d− thừa. Trong khi biểu diễn chắc chắn không phải là tối −u vì có d− thừa, nó gia tăng xác suất tìm nhân tố hình dạng chung khi hình dạng t−ơng ứng đ−ợc giới thiệu trong ảnh, thậm chí chúng bị suy giảm hoặc tùy thuộc vào một phần sự nghẽn. Tất cả các thử nghiệm đ−ợc giới thiệu ở mục 5 đề cập tới đối sánh dựa trên mã hóa cục bộ sử dụng F=5, N=45, theo đó các kết quả thỏa mãn tốt nhất. Tiến hành tại một các tham số tổng quan này đ−ợc cố định cho tất cả các thử nghiệm và không cần xác định lại bởi ng−ời dùng. - 72 - Để giới thiệu một mức đ−ờng L1; mỗi đoạn bằng phẳng và mỗi cặp điểm trên đ−ờng thẳng t−ơng tự và đậm với cung tròn. Hình 3.2 : Mã hóa bán cục bộ sự không đổi t−ơng tự. Phía trái : một minh họa dựa trên đ−ờng mảnh. a) đặt P1 và P2 cả các điểm đậm khi thực sự với mảnh hoặc điểm cuối cùng cho segment đ−ợc tách khi thực sự với đoạn bằng phẳng. Để cặp đoạn đậm D với những điểm này. b) Bắt đầu chậm tiến từ P … P1 với Dgọi P1 là đoạn đậm của L hoặc Thogonoil tới D. Bắt đầu từ P2 gọi P2 đoạn đậm tiếp theo của L hoặc Thogonal tới D. c) Tìm điểm giao điểm giữa P1 và D và giữa P2 và D. Gọi là R1 , R2. d) Chuẩn hóa tọa độ của phân bố điểm N trên ảnh của chuẩn hóa chiều dài F; trung tâm tại C. Giao diện điểm của L với đ−ờng phân giác (R1,R2) bằng tọa độ chuẩn hóa có nghĩa là tọa độ trong khoảng t−ơng đ−ơng định nghĩa bởi điểm R1, R2 trên bản đồ chạy từ (- 2 1 ,0),( 2 1 ,0) t−ơng ứng. Là mã hóa F=5. Khi chiều dài của chúng quá nhỏ với thừa nhận chiều dài của đ−ờng phân đoạn (R1,R2), kết quả nhân tố hình dạng tự nó gối lên nhau(có sự chồng lấn giữa các kết quả thu đ−ợc). Hình 3.3 : mã hóa sự không đổi t−ơng đ−ơng bán cục bộ. Đ−ờng phải : tổng quan 19 nhân tố (F=5, N=45) 12 trong số chúng dựa trên đ−ờng mảnh, còn - 73 - lại là đ−ờng đậm. Biểu diễn khá thừa. ở đây chỉ biểu diễn ba nhân tố hình dạng chuẩn hóa, hai nhân tố hình dạng thu đ−ợc từ đ−ờng mảnh một nhân tố hình dạng từ đ−ờng đậm. Hình 3.3: Mã hoá sự không đổi t−ơng đ−ơng bán cục bộ 3.4.2.2. Mã hóa / Chuẩn hóa quan hệ bất biến Minh họa trong hình 3.4. Nh− đã thực hiện ở việc chuẩn hóa sự t−ơng đồng không đổi, tham số thi hành đ−ợc sửa từ F=5 N=45. Hình 3.5 chỉ ra một vài hình dạng đ−ợc trích chọn từ đ−ờng đơn giản cho các tham số lựa chọn này. Mã hóa thực tế giảm d− thừa so với thủ tục mã hóa t−ơng đồng. Bởi vì thực tế cấu trúc của khung cục bộ quan hệ không đổi lạm dụng nhiều sự miễn c−ỡng trên khung hơn là khung t−ơng đồng không đổi. 3.4.3. Từ chuẩn hóa nhân tố hình dạng đến đặc tr−ng độc lập. Giải thích thủ tục ứng dụng để trích chọn vài đặc tr−ng từ các nhân tố hình dạng. Theo kinh nghiệm thu đ−ợc đồng thời ba yêu cầu đặc tr−ng (minh họa ở hình 3.6). Mỗi đoạn cung Jordan C đ−ợc chia thành 5 đoạn con chiều dài bằng nhau. Mỗi đoạn đ−ợc chuẩn hóa bằng bản đồ dây cung giữa điểm đầu và điểm cuối trên trục ngang. Điểm đầu là điểm gốc : kết quả “ Đoạn cung nhỏ đ−ợc chuẩn hóa “ là 5 đặc tr−ng C1, C2, …, C5 ( mỗi các t−ơng ứng Ci có 9 điểm riêng biệt. Các đặc tr−ng này là độc lập; tuy nhiên C1 … C5 đem lại : nó có thể tái thiết lại hình dạng gốc của chúng : mục đích của sự trọn vẹn đặc tr−ng tổng quan thứ 6. C6 đ−ợc tạo ra từ điểm cuối của 5 đoạn trên, trong khung chuẩn hóa. Cho - 74 - mỗi đoạn của mức đ−ờng. Đặc tr−ng hình dạng đã giới thiệu tạo ra từ ba đặc tr−ng này C1 … C6. Để thu đ−ợc một biểu diễn quan hệ không đổi của các mức đ−ờng L, mỗi đoạn bằng, mỗi cặp điểm trên cùng đ−ờng thẳng là đậm đối với cung thực hiện. Hình 3.4 : Mã hóa bán cục bộ mối quan hệ không đổi. Nhân tố hình dạng đ−ợc mã hóa dựa trên đ−ờng mảnh D. a) Đặt P1, P2 là điểm đậm khi thực tế với mảnh hoặc điểm kết thúc cho tách đoạn khi thực tế với đoạn bằng. Đề cập đ−ờng đậm D với các điểm này. b) Bắt đầu từ P2 trừ đoạn đậm tiếp theo với L, đó là song song với D. Gọi là D’. c) Để cặp đ−ờng thẳng song song D và đặt tại 3 1 và 3 2 , của khoảng cách từ D tới D’. Gọi là D1 và D2 t−ơng ứng. d) Bắt đầu từ P2 tìm điểm giao nhau tiếp theo giữa L và D1, L và D2. Xem xét đoạn thẳng T1 định nghĩa bởi hai điểm này. e) Bắt đầu ng−ợc lại từ P1, tìm điểm đậm tr−ớc đó song song L và T1 gọi là T2. f) Định nghĩa điểm R1, R2 và R3 là điểm cắt giữa D và T2, D và T1, D’ và T2 t−ơng ứng. Hình 3.4: - 75 - g) Điểm R1, R2, R3 định nghĩa nh− một quan hệ cơ bản. Chuẩn hóa quan hệ đ−ợc sửa t−ơng ứng bằng bản đồ {R1, R2, R3} và {(0,0), (1,0), (0,1)} nếu {R1, R2, R3} là một khung trực tiếp và {(0,0), (1,0), (0,-1)} nếu không phải. h) Mã hóa : xem xét điểm giao nhau giữa L và đ−ờng thẳng cách đều từ D và D’ ( điểm đầu bắt đầu P2). Gọi nó là chuẩn hóa C của L chiều dài 2 F tại cả hai ảnh của C. L−u trữ phân bố điểm N trên dạng chuẩn hóa đ−ờng cong. Hình 3.5 : mã hóa hình dạng bán cục bộ quan hệ bất biến. Đ−ờng trên phía phải phát sinh từ 7 nhân tố hình dạng (F=5, N=45); 3 trong số chúng đ−ợc biểu diễn ở đây.Tr−ớc có xi(S) = Ci ( i ∈ (1, …, 6) mỗi i ∈ {1, …, 5}, Ei = (R 2)9. E6= (R 2)6 và khoảng cách di giữa chúng là L ∞ Trong hình 3.6, mã hóa sự t−ơng đồng không đổi. Phác họa a) Hình dạng gốc nh− cung Jordan trong khoảng đ−ợc chuẩn hóa dựa trên đ−ờng mảnh. Cả giới hạn của cung Jordan đ−ợc đề cập đ−ợc rõ ràng với đ−ờng đậm : biểu diễn này đ−ợc chia thành 5 đoạn C1, C2, C3, C4, C5. - 76 - Phác họa b) Mỗi một hình đ−ợc chuẩn hóa và đặc tr−ng số 6 tạo ra điểm cuối của những đoạn này đ−ợc xây dựng. Hình 3.6: mã hoá sự t−ơng đồng không đổi Khả năng khác, điều tra việc sử dụng phân tích thành phần cơ bản PCA [28]. Mặc dù PCA không cung cấp đặc tr−ng độc lập nh−ng nó cũng không phải là chính xác nhất. Khi này, tính toán số cảnh báo sai xuất hiện vẫn có giá trị. Tuy nhiên, kết quả không tốt nh−ng chúng vẫn có PCA thực tế cho phép từ một giới hạn vốn có: nó là thừa nhận bền vững không gian đặc tr−ng tuyến tính. Điều này rõ ràng không đúng với không gian hình dạng. 3.5. Thảo luận Trong phần này đề cập tới nhân tố hình dạng nh− một đoạn của mức đ−ờng đủ độ t−ơng phản. Định nghĩa này theo một phân tích yêu cầu nhận dạng hình dạng. Thay đổi độ t−ơng phản ít và sự tập trung trong tính toán( vùng, thay đổi mức chói ở đâu) là thiết thực. Mục đích để giới thiệu ph−ơng pháp để tính toán NFA của đối sánh của một vài nhân tố hình dạng tiến tới phân lớp không đổi. Tính toán số l−ợng này rất hữu ích bởi nó tiến tới tới chấp nhận hay phủ định ng−ỡng cho đối sánh nhân tố hình dạng. Luật ra quyết định để dựa trên sự cân nhắc các đối sánh với NFA < 1(hoặc 10-1 nếu đ−ợc đề cập tới việc tách chính - 77 - xác), việc tự động mức ng−ỡng khoảng cách phụ thuộc vào CSDL và phụ thuộc vào truy vấn. Dĩ nhiên, với đoạn mức đ−ờng không đủ để quyết định có hay không 1 đối t−ợng trích ra từ ảnh. Tuy nhiên, biên đối t−ợng trùng khớp tốt nhất với các đoạn mức đ−ờng, vì thế có thể đánh giá để tính toán. B−ớc tiếp theo là kết hợp các đối sánh bằng cách tính toán kết cấu không gian của chúng. Thật vậy, có thể thấy trong các thử nghiệm đ−ợc giới thiệu, đối sánh sai(đối sánh không t−ơng ứng với các đối t−ợng giống nhau) không đ−ợc phân bố rõ ràng trên một ảnh, ng−ợc lại hoàn toàn với nh− đối sánh chính xác. Mỗi cặp đối sánh nhân tố hình dạng tiến tới 1 biến đổi xác định giữa các ảnh, t−ơng ứng nh− một đối t−ợng trong biến đổi không gian. Từ đó các đối sánh có ý nghĩa không gian chặt chẽ phải t−ơng ứng nh− cluster trong không gian biến đổi, việc tách các đối sánh có ý nghĩa có thể tính toán nh− việc thực hiện cluster. Hoàn thành nhiệm vụ này chính là phát triển thuật toán cluster không giám sát mà vẫn dựa trên ph−ơng pháp cotrario. Đồng thời, kết hợp thông tin không gian có sẵn bằng đối sánh nhân tố hình dạng sẽ củng cố cho nhận dạng nhân tố hình dạng của ph−ơng pháp ra quyết định Contrario. - 78 - Ch−ơng 4 Thử nghiệm 4.1. Thử nghiệm ph−ơng pháp nền Tính toán xác suất PFA(S, δ) của một nhân tố hình dạng bằng cách thay đổi tại một khoảng cách thấp hơn δ để một truy vấn hình dạng S là đúng với giả thuyết (A) độc lập dựa trên khoảng cách giữa các thuộc tính. Dĩ nhiên dựa vào độ chính xác có thể mang tới giá trị NFA(S, δ) đủ lớn phụ thuộc giá trị của giả thuyết độc lập (A). Số các cảnh báo sai mong muốn trong số tất cả các đối sánh có ý nghĩa ε với truy vấn hình dạng ở mức thấp hơn của ε. Tuy nhiên không thể cảnh báo riêng và đối sánh thực tế : chúng chỉ tách khi quan sát. Hiện tại, nguyên tắc Helinholtz nói rõ không thực hiện tách các đối t−ợng lẫn “nhiễu”. Mọi đối sánh ý nghĩa ε mà có nhiễu sẽ coi nh− cảnh báo sai. Trong mỗi tr−ờng hợp, sau khi kiểm tra yêu cầu trị trung bình ε của nhiễu, chỉ ra rằng tr−ờng hợp này NFA là dự báo khá tốt số hình dạng đ−ợc tách. Giả thuyết độc lập đủ giá trị, vì vậy yêu cầu phụ thuộc trị trung bình cảnh báo sai ε trong số ε đối sánh có ý nghĩa còn lại. Thử nghiệm đầu tiên, kiểm tra ng−ỡng tách trên mọi ph−ơng thức đơn giản. Xem xét CSDL và truy vấn một vài không gian với việc gia tăng số l−ợng đặc tr−ng độc lập (thay thế cho hình dạng đã chuẩn hóa). Mặc dù trong tr−ờng hợp này, nhân tố hình dạng không lấy từ đ−ờng cong Jordan, ph−ơng thức nền là có khả năng thực hiện. Trong cảnh, các nhân tố hình dạng đ−ợc đề cập hoàn toàn thích hợp giả thuyết đặc tr−ng độc lập. Bảng 4.1 chỉ ra số các cảnh báo sai dự báo chính xác cho CSDL có kích th−ớc khác nhau : số tách với NFA thấp hơn ε là khoảng cách thực tế ε . - 79 - Bảng 4.1 : Trung bình lớn hơn 10 mẫu. Số tách có ý nghĩa ε = 1 mâu thuẫn ε. Hàng đầu tiên : CSDL có 100 hình dạng, thứ 2 có 50 hình dạng, thứ 3 có 10 hình dạng. Dĩ nhiên, ph−ơng pháp này không thực tế với nhân tố hình dạng xuất hiện ngẫu nhiên. Nói cách khác, nhân tố hình dạng t−ơng ứng với đoạn cung Jordan và bởi vậy nó bị phân chia c−ỡng bức. Đặc tr−ng nhân tố hình dạng thu đ−ợc từ thủ tục chuẩn hóa, giới thiệu một vài cấu trúc t−ơng đ−ơng (ví dụ : nhân tố hình dạng kết hợp từ các điểm mảnh với cấu trúc chung) để số l−ợng “ trọng số sự phụ thuộc ” giảm bớt bởi vì những cái này có hai mặt. ảnh nhiễu, bảng 2 chỉ ra số tách không là dự đoán chính xác nh− trong kinh nghiệm dự đoán, cuối cùng mỗi giá trị ε nhỏ. Tuy nhiên, để biên độ là đúng, không phụ thuộc vào kích th−ớc của CSDL cần phải thiết lập ng−ỡng số cảnh báo sai trên nguyên tắc Helrholtz. Ph−ơng pháp d−ới đây, một đối sánh là đ−ợc coi nh− một quan hệ mật thiết nếu nó không xuất hiện trong ảnh có nhiễu. Phụ thuộc bảng 2, đối sánh với mức thấp hơn 0,1 để chắc chắn không có nhiễu trắng. Bảng 2 đối sánh với NFA < 0,1 đ−ợc chắc chắn để khá giống với trong nhiễu trắng. Nếu muốn chắc chắn sự tin cậy cao trong đối sánh để tách, chúng ta tiến tới đối sánh có ý nghĩa 0,1 theo kinh nghiệm thực tế. Bảng 4.2 : Đoạn chuẩn hóa của đ−ờng mức có nhiễu trắng. - 80 - 4.2. Thử nghiệm Contrario 4.2.1. Hai ảnh không quan hệ với nhau Mục tiêu của thử nghiệm này là để kiểm tra phạm vi chính của ph−ơng pháp đề xuất: số các cảnh báo sai NFA là một −ớc l−ợng số các đối sánh thay đổi. Hình 4.1 có thể thấy 2 kết quả biểu diễn đ−ợc mô tả nh− thế nào khi đề cập tới các ảnh khác. Nhân tố hình dạng đ−ợc chuẩn hoá sự t−ơng đồng bất biến của mức đ−ờng có ý nghĩa từ những cái đ−ợc tìm kiếm đầu tiên trong số các nhân tố hình dạng đ−ợc chuản hoá từ bức ảnh thứ 2. Chỉ những đối sánh có ý nghĩa 1 đ−ợc khôi phục(NFA của đối sánh này <1) nh− ở Pro 3. 1 là mong đợi nhất của một đối sánh có ý nghĩa. Mặc dù ph−ơng pháp không làm xáo trộn giữa đối sánh tốt và đối sánh sai, NFA mang lại 1 −ớc l−ợng tốt” đối sánh tốt nh− thế nào” Trong hình 4.1, hai ảnh không liên quan. ảnh gốc (bên trái), mức đ−ờng có ý nghĩa (ở giữa), 846 hình dạng đ−ợc chuẩn hoá ở trên đ−ợc tìm kiếm trong số 281 hình dạng đ−ợc chuẩn hoá từ bức ảnh thứ 2. Chỉ đối sánh có ý nghĩa 1 đ−ợc tách (bên phải) NFA bằng 0.2. Đối sánh này t−ơng ứng đoạn mức đ−ờng khá thô đ−ợc lấy ngẫu nhiên. Hình 4.1: ảnh và mức đ−ờng có ý nghĩa - 81 - 4.2.2. Méo dạng quan sát xa gần Không ngẫu nhiên khi thực hiện ph−ơng pháp quan hệ tốt hơn ph−ơng pháp t−ơng đồng. Khi phân chia với ảnh liên hệ dù chỉ có 1 thay đổi mối quan hệ. Trong thử nghiệm thứ hai, chỉ ra ph−ơng pháp quan hệ thực hiện tốt hơn(với chú ý NFA thấp nhất có thể tìm kiếm). So với ph−ơng pháp t−ơng đồng, khi ứng dụng vào ảnh thực liên quan vừa phải tới biến đổi xa gần ít. Hai ảnh đ−ợc đề cập trong thử nghiệm này(thử nghiệm Hitchcock) là hai ảnh chụp của cùng một cảnh. Chỉ ra ở hình 4.2 với đ−ờng mức t−ơng ứng của chúng. Đối với ph−ơng pháp quan hệ bán cục bộ không đổi, 1150 và 853 nhân tố hình dạng đ−ợc trích chọn từ ảnh mục tiêu và từ CSDL t−ơng ứng. Số các đối sánh ý nghĩa 1 đ−ợc tách là 16. 16 nhân tố hình dạng đ−ợc đối sánh này đ−ợc chỉ ra trên ảnh, trong hình 4.3. Không đối sánh sai nào bị tách, và mọi đối sánh NFA của chúng <0.1. Đối sánh tốt nhất chỉ ra trong hình 4.2, NFA nghiên cứu bằng 6,5. 10-11. Giá trị này rõ ràng rất thấp, đề cập tới ý t−ởng đối sánh hoàn hảo trong thử nghiệm với số cảnh báo sai: 26 105.2853 8531150 −ì=ì Khi phân bố theo kinh nghiệm của khoảng cách ảnh đích đ−ợc học sử dụng duy nhất CSDL ảnh đã đề cập. Hình 4.2: chỉ ra đối sánh có ý nghĩa đ−ợc tách sử dụng ph−ơng pháp nhận dạng bán cục bộ bất biến. Trong tr−ờng hợp này 2.33 và 1463 nhân tố hình dạng đ−ợc trích chọn từ annhr và CSDL t−ơng ứng. ph−ơng pháp t−ơng đồng dẫn tới trích chọn nhiều nhân tố hình dạng hơn ph−ơbng pháp quan hệ, đó là lý do tại sao nhiều đối sánh có ý nghĩa 1 đ−ợc tách, trong tr−ờng hợp này đối sánh có ý nghĩa cho ph−ơng pháp t−ơng đồng đ−ợc chỉ ra ở hình 4.5. Mức NFA thấp nhất tìm they với ph−ơng pháp t−ơgn đồng là 3.8*10-8 và t−ơgn ứng các nhân tố hình dạng đ−ợc tách biểu diễn ở hình 4.3. Trong hình 11b,c t−ơgn ứng đối sánh nhân tố hình dạng tại ε<0.1 và cho NFA là: 0.1<NFA<1. Chú ý : không có danh sách có - 82 - ý nghĩa 10-1 nào là đối sánh sai và các nhân tố hình dạng theo tổng quan cục bộ hơn so với đối sánh hình 4.5c. Các nhân tố hình dạng tổng quan kém chính xác t−ơng đ−ơng nh− biến đổi phép chiếu. Trong hình 4.2, thử nghiệm hitchcook: ảnh gốc (t−ơng ứng 2 ảnh chụp cùng 1 cảnh và mức đ−ờng t−ơng ứng của chúng đ−ợc mã hoá. ảnh phía trên là ảnh đích. Trong ảnh đích 307 mức đ−ờng có ý nghĩa đ−ợc tách và 266 mức đ−ờng có ý nghĩa đ−ợc tách trong CSDL ảnh.). NFA thấp nhất tìm kiếm với ph−ơng pháp t−ơng đồng (3,8*10-8) lớn hơn so với mức NFA thấp nhất ở ph−ơng pháp quan hệ (6,5*10-11). NFA khá thấp trong ph−ơng pháp quan hệ so với ph−ơng pháp t−ơng đồng, t−ơng ứng nh− phép biến đổi phép chiếu áp dụng ở đây xấp xỉ cục bộ bằng biến đổi quan hệ tốt hơn biến đổi t−ơng đồng. Hai đối sánh sai, NFA >0.1 thấy ở hình 4.5c. Hình 4. chỉ ra nhân tố hình dạng của các đối sánh sai này, khi thêm vào nhân tố hình dạng đ−ợc chuẩn hoá biểu diễn ở khung đ−ợc chuẩn hoá. Chú ý ng−ỡng khoảng cách t−ơng ứng với mỗi NFA là đủ lớn vì vậy không có đối sánh tốt nào bị lỗi. Mặc dù ph−ơng pháp đ−ợc giới thiệu không xác định xác suất này rất thấp. Hình 4.2: thử nghiệm hitchcook - 83 - Trong hình 4.3 có 16 đối sánh có ý nghĩa giữa các nhân tố hình dạng theo ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi. Không đối sánh sai nào đ−ợc tách (trong ảnh mọi đối sánh có ý nghĩa t−ơng ứng đoạn giống nhau của đối t−ợng) mọi phép tách chỉ ra NFA <0.1. NFA thấp nhất NFA =6,5 10-11 Hình 4.3: Ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi Hình 4.4: ph−ơng pháp nhận dạng quan hệ bán cục bộ không đổi Trong hình 4.4, đối sánh chỉ ra mức NFA thấp nhất 6.5 10-11 4.2.3. Quan hệ với sự nghẽn cục bộ và thay đổi độ t−ơng phản Thử nghiệm sau cốt yếu so sánh mã hoá trích chọn từ hai điểm quan ssát của bức hoạ Monalisa( hình 4.5). Mã đ−ợc trích chọn từ truy vấn (11332 mã) đ−ợc tìm thấy trong số các mã đ−ợc trích chọn từ CSDL ảnh (11833 mã). Nhân tố hình dạng đ−ợc chuẩn hoá chú ý biến đổi t−ơng đ−ơng. Chú ý ảnh gốc là ảnh chụp từ bảo tàng. - 84 - Hình 4.5 ph−ơng pháp nhận dạng bán cục bộ : sự t−ơng đồng không đổi: các đối sánh sai(2) có thể thấy ở hình c NFA > 0.1 a: 26 đối sánh NFA< 1, b: 12 đối sánh NFA< 0.1, c:14đốisánhNFA∈(0.1ữ1) Ph−ơng pháp nhận dạng cục bộ sự t−ơng đồng không đổi: đối sánh chỉ ra mức NFA thấp nhất (3.8 10-8). Trong hình 4.6 chỉ ra bên trái: tập các đoạn đ−ờng mức trong ảnh gốc đ−ợc đối sánh 1 đoạn mức đ−ờng trong CSDL ảnh t−ơng ứng. NFA <1 và phía phải là tập các nhân tố hình dạng từ CSDL ảnh t−ơng ứng tại ảnh cuối cùng trong truy vấn ảnh. Thuật toán nhận ra 55 đối sánh có ý nghĩa. Chỉ 5 đối sánh sai có thể thấy trong số chúng. Có NFA∈(1, 10-1) sự thật, 36 đối sánh chỉ ra 1 NFA <10-1 Hình 11 Hình 4.5 nhận dạng bán cục bộ - 85 - Hình 4.6: Tập các đoạn đ−ờng mức đối sánh với ảnh trong CSDL Trong hình 4.7, 2 đối sánh sai NFA>0,1 ph−ơng pháp bán cục bộ t−ơng đồng không đổi. Mỗi NFA từ đ−ờng cong chỉ ra sự biến đổi cục bộ. Nh−ng hình dạng chung gióng nhau, nh− ảnh gốc thể có thể dựa vào nhân tố hình dạng đ−ợc chuẩn hoá. Hình 4.7: ph−ơng pháp bán cục bộ t−ơng đồng không đổi a- Đối sánh sai NFA= 0,64; b- Đối sánh sai N=0.68 Trong hình 4.8, ảnh gốc bên trái và mức đ−ờng có ý nghĩa bên phải. ảnh trên ảnh d−ới :truy vấn ảnh và mức đ−ờng của nó.Mã hoá từ truy vấn hình dạng đ−ợc tìm kiếm trong số mã từ CSDL ảnh. Chuẩn hoá ở đay phải chú ý đến biến đổi t−ơng đ−ơng. - 86 - Hình 4.8: ảnh gốc và mức đ−ờng có ý nghĩa Trong hình 4.9, ảnh Menima 55 đối sánh có ý nghĩa, một nửa trong số chúng có NFA < 10-3, đối sánh tốt nhất có NFA=4*10-4. để mỗi đoạn đậm của mức bên phải t−ơng ứng đoạn đậm phía trái . Hình 4.9: ảnh Menima và mức đ−ờng có ý nghĩa Trích trọn đặc tr−ng độc lập đ−ợc giới thiệu khá thực tế và cung cấp khá nhiều kết quả kinh nghiệm. ( Trong sense có nghĩa là đối sánh t−ơng ứng với nhân tố hình dạng thành đối t−ơng t−ơng ứng). - 87 - 4.3. Thảo luận Phần này đ−a ra một vài thử nghiệm minh hoạ cho ph−ơng pháp Contraio để chuẩn hoá mức đ−ờng. Mặc dù ảnh và đoạn mức đ−ờng thêm vào ảnh đ−ợc chỉ ra, ng−ời đọc có thể giữ luật ra quyết định thực tế với nhân tố hình dạng đã đ−ợc chuẩn hóa. Tuy nhiên kết quả t−ơng ứng với đoạn mức đ−ờng (không chuẩn hóa hình dạng trong một vài cảnh) đ−ợc chỉ ra ở đây rõ ràng. Gọi đối sánh sai trong là đối sánh thực sự nó có t−ơng ứng với đối t−ợng t−ơng tự nh− thế nào. Rồi đ−a đối sánh ngữ nghĩa chính xác. Tách các đối sánh không giống nh− xuất hiện bởi thay đổi hoặc chứng tỏ chính xác, đối sánh không chắc rằng đ−ợc phát sinh nhiễu hơn từ ph−ơng pháp nền ( sửa ứng với NFA ng−ỡng 1). Đối sách sai phát sinh từ NFA lớn hơn 10-1. Đơn giản đặt ng−ỡng NFA = 10-1. - 88 - Kết luận Sau thời gian nghiên cứu và tìm hiểu về ph−ơng pháp contrario cho nhận dạng nhân tố hình dạng tôi đã đạt đ−ợc một số kết quả sau: - Nắm đ−ợc ph−ơng pháp tách nhóm trong thủ tục với nhận dạng và tìm kiếm hình dạng. - Nắm đ−ợc ph−ơng pháp ra quyết định dựa vào việc đối sánh hình dạng truy vấn với hình dạng trong CSDL và số các cảnh báo sai NFA. - Tìm hiểu, phân tích đ−ợc phần thử nghiệm của ph−ơng pháp. Với mục đích nghiên cứu tìm hiểu để áp dụng ph−ơng pháp ra quyết định Contrario cho nhận dạng hình dạng tiến tới là nhận dạng đối t−ợng trong các ảnh phức tạp. Với những kết quả đã đạt đ−ợc trong thời gian nghiên cứu vừa qua, tôi nhận thấy mình có thể tiếp tục nghiên cứu để hoàn thiện ph−ơng pháp này hơn nữa. Hy vọng luận văn này sẽ giúp ích phần nào cho những ng−ời bắt đầu tìm hiểu về lĩnh vực mới này. Tôi xin chân thành cảm ơn: TS Nguyễn Kim Anh, ng−ời đã trực tiếp h−ớng dẫn và giúp đỡ tôi trong thời gian làm luận văn. Trung tâm Đào tạo và Bồi d−ỡng Sau Đại học - Tr−ờng Đại học Bách khoa Hà Nội; các thầy cô giáo trong Khoa Điện tử, tr−ờng ĐHCN Hà Nội, đã giúp đỡ tôi về mặt thời gian cũng nh− sự động viên rất lớn của bạn bè ng−ời thân về mặt tinh thần trong thời gian thực hiện đề tài. - 89 - Tài liệu tham khảo 1. F. Cao, J. Delon, A. Desolneux, P. Musé, F.Sur (2005), “A unified framework for detecting and application to shape recognition”, 2. Dengsheng Zhang,(2002), Image Retrieval Based on Shape, Monash University. 3. [ZHA01] D.S. Zhang and G.Lu. Segmentation of Moving Objects in Image Sequence: A revieww. Circuits, Systems and Signal Processing( Special Issue on multimedia) 4. Frédéric Cao, “An a contrario decision method for shape elemet recognition” 5. Anil K.Jain(2002), Fundamentals of Digital Image Processing, 6. G.Dudek, J.k.Tsotsos (1997). Shape Representation and Recognition from multiscale Curvature - 90 - Tóm tắt luận văn Đề tài: “Nghiên cứu ph−ơng pháp nhận dạng hình dạng” với mục đích nghiên cứu ph−ơng pháp Contrario cho nhận dạng nhân tố hình dạng từ các công đoạn cơ bản của quá trình nhận dạng nh− biểu diễn hình dạng, tách nhóm các nhân tố hình dạng thành hình dạng và đặc biệt là ra quyết định dựa vào NFA( số cảnh báo sai) Nội dung của đề tài bao gồm: - Nghiên cứu ph−ơng pháp biểu diễn hình dạng. - Nghiên cứu ph−ơng pháp thực hiện Cluster chính xác. - Nghiên cứu ph−ơng pháp ra quyết định Contrario cho nhận dạng nhân tố hình dạng. - Thử nghiệm ph−ơng pháp ra quyết định Contrario cho nhận dạng hình dạng Trong luận văn tác giả giới thiệu về ph−ơng pháp Contrario. Qua việc nghiên cứu này tác giả đãgiới thiệu ph−ơng pháp nhận dạng dựa trên số cảnh báo sai tiến bộ hơn so với một số ph−ơng pháp đã có mà thực hiện nhận dạng dựa trên đối sánh về khoảng cách. Nội dung của luận văn đ−ợc thể hiện qua 4 ch−ơng: Ch−ơng 1: Tổng quan về hệ thống điều khiển giám sát Ch−ơng 2: Tách nhóm Ch−ơng 3: Ph−ơng pháp ra quyết định Contrario Ch−ơng 4: Thử nghiệm • Từ khoá chính của luận văn: ” nhận dạng, tách nhóm, ra quyết định, nhân tố hình dạng”