KJ

Edge detection
Dari Wikipedia, ensiklopedia bebas
Langsung ke: navigasi, cari
Fitur deteksi
Corner.png
Output dari sudut khas algoritma deteksi
Edge detection
Cerdik
Cerdik-Deriche
Diferensial
Sobel
Bunga titik deteksi
Corner deteksi
Harris operator
Shi dan Tomasi
Tingkat kurva kelengkungan
SUSAN
FAST
Blob deteksi
Laplacian of Gaussian (LOG)
Perbedaan Gaussians (DoG)
Determinan dari Hessian (DOH)
Maksimal stabil extremal daerah
PCBR
Ridge deteksi
Deteksi fitur affine invariant
Affine bentuk adaptasi
Harris affine
Goni affine
Fitur deskripsi
SIFT
SURF
GLOH
LESH
Ruang skala
Ruang skala-aksioma
Pelaksanaan rincian
Pyramids
l • d • s

Edge detection adalah suatu terminologi dalam pengolahan gambar dan visi komputer, khususnya di bidang fitur fitur deteksi dan ekstraksi, untuk mengacu pada algoritma yang bertujuan untuk mengidentifikasi titik-titik dalam gambar digital di mana perubahan kecerahan gambar tajam atau lebih formal memiliki diskontinuitas.
Isi
[hide]

* 1 Motivasi
* 2 Edge properti
* 3 model tepi sederhana
* 4 Mengapa deteksi tepi adalah non-tugas sepele
* 5 Pendekatan untuk deteksi tepi
o 5,1 cerdik deteksi tepi
o 5,2 orde pertama lain metode
o 5,3 Thresholding dan menghubungkan
o 5,4 orde Kedua pendekatan untuk deteksi tepi
+ 5.4.1 Differential deteksi tepi
o 5,5 Fase kesesuaian berdasarkan deteksi tepi
* 6 Referensi
* 7 Lihat juga

[sunting] Motivasi

Tujuan tajam mendeteksi perubahan dalam kecerahan gambar adalah untuk menangkap peristiwa-peristiwa penting dan perubahan dalam dunia properti. Dapat ditunjukkan bahwa di bawah asumsi yang agak umum untuk gambar model pembentukan, diskontinuitas dalam kecerahan gambar kemungkinan akan sesuai dengan [1] [2]:

* Diskontinuitas secara mendalam,
* Diskontinuitas permukaan orientasi,
* Perubahan dalam sifat-sifat material dan
* Variasi dalam adegan iluminasi.

Dalam kasus yang ideal, akibat penerapan sebuah detektor tepi ke foto dapat mengakibatkan terhubung satu set kurva yang menunjukkan batas-batas obyek, batas dan juga tanda-tanda permukaan kurva yang sesuai dengan orientasi diskontinuitas di permukaan. Dengan demikian, menerapkan sebuah detektor ke tepi gambar tersebut dapat secara signifikan mengurangi jumlah data yang akan diproses dan karenanya menyaring informasi yang mungkin dianggap sebagai kurang relevan, sambil menjaga sifat struktural penting dari suatu gambar. Jika langkah deteksi tepi berhasil, tugas selanjutnya menafsirkan isi informasi gambar asli karenanya mungkin secara substansial disederhanakan. Sayangnya, bagaimanapun, tidak selalu mungkin untuk mendapatkan yang ideal seperti tepi dari kehidupan nyata gambar dari kompleksitas moderat. Tepi-tepi yang diambil dari gambar non-sepele sering dihambat oleh fragmentasi, yang berarti bahwa kurva tepi tidak terhubung, hilang segmen tepi serta ujung palsu tidak sesuai dengan fenomena menarik di gambar - sehingga memperumit tugas selanjutnya menafsirkan data gambar [ 3].
[sunting] Edge properti

Tepi diekstraksi dari gambar dua dimensi dari adegan tiga dimensi dapat digolongkan sebagai sudut pandang baik sudut pandang tergantung atau mandiri. Sebuah sudut pandang tepi independen biasanya mencerminkan sifat-sifat yang melekat dari benda tiga dimensi, seperti tanda-tanda permukaan dan bentuk permukaan. Sebuah sudut pandang tepi tergantung dapat berubah sejalan dengan perubahan sudut pandang, dan biasanya mencerminkan geometri adegan, seperti objek occluding satu sama lain.

Tepi tipikal mungkin misalnya menjadi perbatasan antara blok warna merah dan satu blok kuning. Sebaliknya garis (seperti dapat diekstraksi oleh punggungan detektor) bisa menjadi sejumlah kecil piksel warna yang berbeda pada latar belakang yang sebenarnya tidak berubah. Untuk baris, mungkin karena itu biasanya menjadi salah satu ujung di setiap sisi dari garis.

Tepi cukup memainkan peran penting dalam banyak aplikasi image processing, khususnya untuk visi mesin sistem yang menganalisis adegan buatan manusia dikontrol objek di bawah kondisi pencahayaan. Selama tahun-tahun belakangan, bagaimanapun, substansial (dan sukses) penelitian juga telah dibuat pada visi komputer metode yang tidak secara eksplisit mengandalkan deteksi tepi sebagai pre-langkah pengolahan.
[sunting] A simple model tepi

Meskipun literatur tertentu telah dianggap sebagai langkah ideal deteksi tepi, pinggiran gambar yang diperoleh dari alam biasanya tidak sama sekali langkah ideal tepi. Sebaliknya mereka biasanya dipengaruhi oleh satu atau beberapa efek sebagai berikut:

* Fokus blur yang disebabkan oleh kedalaman terbatas-of-field dan penyebaran titik fungsi terbatas.
* Kabur penumbral disebabkan oleh bayangan yang diciptakan oleh sumber cahaya non-radius nol.
* Bayangan pada objek yang halus

dan sejumlah peneliti telah menggunakan langkah merapikan tepi Gaussian (kesalahan fungsi) sebagai perpanjangan sederhana langkah ideal tepi model model untuk efek blur di tepi aplikasi praktis. [4] [3] Dengan demikian, satu-dimensi f gambar yang memiliki tepat satu ujung diletakkan pada x = 0 mungkin akan dimodelkan sebagai:

f (x) = \ frac (I_r - I_l) (2) \ left (\ operatorname (erf) \ left (\ frac (x) (\ sqrt (2) \ sigma) \ right) + 1 \ right) + I_l .

Di sisi kiri dari tepi, intensitas adalah I_l = \ lim_ (x \ Rightarrow - \ infty) f (x), dan kanan dari tepi itu I_r = \ lim_ (x \ Rightarrow \ infty) f (x) . Parameter σ skala disebut skala mengaburkan tepi.
[sunting] Mengapa deteksi tepi adalah non-tugas sepele

Untuk menggambarkan kenapa deteksi tepi bukanlah tugas sepele, mari kita mempertimbangkan masalah mendeteksi tepi dalam satu dimensi berikut sinyal. Di sini, kita dapat secara intuitif mengatakan bahwa harus ada batas antara ke-4 dan ke-5 piksel.
5 7 6 4 152 148 149


Jika perbedaan intensitas lebih kecil antara ke-4 dan ke-5 pixel dan jika intensitas perbedaan antara piksel tetangga yang berdekatan lebih tinggi, tidak akan mudah untuk mengatakan bahwa harus ada kelebihan dalam wilayah yang sesuai. Selain itu, orang dapat berargumentasi bahwa kasus ini adalah salah satu di mana terdapat beberapa tepi.
5 7 6 41 113 148 149


Oleh karena itu, untuk negara tegas ambang tertentu pada seberapa besar perubahan intensitas antara dua tetangga piksel harus bagi kita untuk mengatakan bahwa harus ada batas antara piksel ini tidak selalu menjadi masalah sederhana. Memang, ini adalah salah satu alasan mengapa deteksi tepi mungkin non-masalah sepele kecuali benda-benda dalam adegan sangat sederhana dan kondisi pencahayaan dapat dikendalikan dengan baik.
[sunting] Pendekatan untuk deteksi tepi

Ada banyak metode untuk deteksi tepi, tetapi kebanyakan dari mereka dapat dikelompokkan ke dalam dua kategori, berbasis pencarian dan nol-persimpangan berbasis. Pencarian berbasis metode mendeteksi tepi dengan terlebih dahulu menghitung ukuran kekuatan tepi, biasanya sebuah derivatif orde pertama ekspresi seperti gradien besar, dan kemudian mencari arah lokal maxima dari besarnya gradien dihitung menggunakan perkiraan dari orientasi lokal tepi, biasanya gradien arah. Nol-persimpangan berdasarkan metode mencari nol penyeberangan di urutan kedua ekspresi derivatif dihitung dari gambar dalam rangka untuk mencari tepi, biasanya nol-penyeberangan dari Laplacian atau nol-penyeberangan dari diferensial non-linear ekspresi, seperti yang akan dijelaskan pada bagian tepi deteksi diferensial berikut di bawah ini. Sebagai langkah pra-pemrosesan untuk deteksi tepi, sebuah panggung meratakan, biasanya Gaussian smoothing, hampir selalu diterapkan (lihat juga noise reduction).

Metode pendeteksian tepi yang telah diterbitkan terutama berbeda dalam jenis penyaring smoothing yang diterapkan dan cara ukuran kekuatan tepi dihitung. Seperti banyak metode pendeteksian tepi bergantung pada gambar perhitungan gradien, mereka juga berbeda dalam jenis penyaring yang digunakan untuk menghitung perkiraan gradien dalam x dan y-arah.

Sebuah survei dari sejumlah metode pendeteksian tepi yang berbeda dapat ditemukan dalam (Ziou dan Tabbone 1998) [5]; lihat juga artikel bebas deteksi tepi dalam Encyclopedia of Mathematics [2] dan Encyclopedia of Computer Science and Engineering [6].
[sunting] cerdik deteksi tepi

Lihai [7] dianggap sebagai masalah matematika yang berasal filter yang optimal diberikan merapikan kriteria deteksi, lokalisasi dan meminimalkan beberapa tanggapan ke satu sisi. Dia menunjukkan bahwa filter optimal diberikan asumsi-asumsi ini adalah jumlah dari empat istilah eksponensial. Ia juga menunjukkan bahwa filter ini dapat juga diperkirakan dengan orde pertama derivatif dari Gaussians. Lihai juga memperkenalkan gagasan maksimum non-penindasan, yang berarti diberi presmoothing filter, titik-titik tepi didefinisikan sebagai titik-titik di mana mengasumsikan besarnya gradien maksimum lokal di arah gradien.

Walaupun karyanya telah dilakukan di masa-masa awal visi komputer, detektor tepi yang cerdik (termasuk variasi) masih merupakan negara-of-the-art detektor tepi. Kecuali prasyarat yang sangat cocok, sulit untuk menemukan detektor tepi yang melakukan secara signifikan lebih baik daripada detektor tepi yang cerdik.

Yang lihai-Deriche detektor [8] adalah berasal dari matematika serupa kriteria sebagai detektor tepi cerdik, walaupun mulai dari sudut pandang yang terpisah dan kemudian menuju ke satu set rekursif filter untuk merapikan gambar, bukan eksponensial penyaring atau filter Gaussian.

Detektor tepi diferensial diuraikan di bawah ini dapat dilihat sebagai suatu reformulasi metode cerdik dari sudut pandang diferensial invariants dihitung dari skala-ruang representasi.
[sunting] Lain orde pertama metode

Untuk memperkirakan gambar gradien dari masukan foto atau versi merapikan itu, operator gradien yang berbeda dapat diterapkan. Pendekatan paling sederhana adalah dengan menggunakan perbedaan utama:

L_x (x, y) =- 1 / 2 \ cdot L (x-1, y) + 0 \ cdot L (x, y) + 1 / 2 \ cdot L (x +1, y). \,
L_y (x, y) =- 1 / 2 \ cdot L (x, y-1) + 0 \ cdot L (x, y) + 1 / 2 \ cdot L (x, y +1). \,

sesuai dengan penerapan penyaring berikut masker untuk data gambar:

L_x = \ begin (bmatrix) -1 / 2 & 0 & 1 / 2 \ end (bmatrix) * L \ quad \ mbox (dan) \ quad L_y = \ begin (bmatrix) 1 / 2 \ \ 0 \ \ -- 1 / 2 \ end (bmatrix) * L

Terkenal dan sebelumnya operator Sobel didasarkan pada filter berikut:

L_x = \ begin (bmatrix) -1 & 0 & 1 \ \ -2 & 0 & 2 \ \ -1 & 0 & 1 \ end (bmatrix) * L \ quad \ mbox (dan) \ quad L_y = \ begin (bmatrix) 1 & 2 & 1 \ \ 0 & 0 & 0 \ \ -1 & -2 & -1 \ end (bmatrix) * L

Mengingat perkiraan seperti orde pertama derivatif, besarnya gradien kemudian dihitung sebagai:

| \ nabla L | = \ sqrt (L_x ^ 2 + L_y ^ 2)

sementara orientasi gradien dapat diperkirakan sebagai

\ theta = \ operatorname (atan2) (L_y, L_x)

Lain orde pertama untuk memperkirakan perbedaan citra operator gradien telah diajukan pada Prewitt lintas operator dan Roberts.
[sunting] Thresholding dan menghubungkan

Sekali kita telah dihitung tepi sebuah ukuran kekuatan (magnitudo gradien biasanya), tahap berikutnya adalah menerapkan ambang batas, untuk memutuskan apakah pinggiran hadir atau tidak pada titik gambar. Semakin rendah ambang batas, semakin tepi akan terdeteksi, dan hasilnya akan semakin rentan terhadap kebisingan, dan juga untuk memilih fitur yang tidak relevan dari gambar. Sebaliknya ambang batas yang tinggi dapat kehilangan halus pinggirnya, atau hasil di tepi terfragmentasi.

Jika tepi thresholding diterapkan hanya untuk gambar besarnya gradien, tepi-tepi yang dihasilkan pada umumnya akan menjadi tebal dan beberapa jenis menipis tepi pasca-pengolahan yang diperlukan. Untuk mendeteksi tepi dengan non-Namun penindasan maksimum, kurva tepi tipis dengan definisi dan piksel pinggir dapat dihubungkan ke ujung poligon dengan sebuah sisi menghubungkan (tepi pelacakan) prosedur. Pada grid diskret, non-tahap penekanan maksimum dapat dilaksanakan dengan memperkirakan arah gradien menggunakan derivatif orde pertama, maka pembulatan gradien arah untuk kelipatan dari 45 derajat, dan akhirnya membandingkan nilai gradien dalam perkiraan besarnya gradien arah.

Sebuah pendekatan yang umum digunakan untuk menangani masalah batas yang tepat untuk thresholding adalah dengan menggunakan thresholding dengan histeresis. Metode ini menggunakan beberapa ambang batas untuk menemukan ujungnya. Kita mulai dengan menggunakan batas atas untuk menemukan mulai dari tepi. Setelah kita memiliki titik awal, kami kemudian menelusuri pinggir jalan melalui gambar pixel by pixel, menandai sebuah tepi setiap kali kita berada di atas batas bawah. Kami berhenti menandai tepi kami hanya ketika kami turun di bawah nilai ambang batas yang lebih rendah. Pendekatan ini membuat asumsi bahwa tepi-tepi cenderung terus-menerus berada dalam kurva, dan memungkinkan kita untuk mengikuti sedikit bagian dari tepi telah kita lihat, tanpa makna bahwa setiap bising pixel dalam gambar ditandai sebagai tepi bawah. Namun, bagaimanapun, kami memiliki masalah untuk memilih parameter thresholding yang tepat, dan sesuai nilai-nilai thresholding dapat bervariasi setiap gambar.
[sunting] Second-order pendekatan untuk deteksi tepi

Beberapa ujung-deteksi operator, bukan berdasarkan urutan kedua turunan dari intensitas. Dasarnya ini menangkap laju perubahan dalam intensitas gradien. Dengan demikian, dalam kasus yang ideal terus-menerus, deteksi nol-penyeberangan dalam menangkap derivatif kedua maxima lokal dalam gradien.

Marr awal-Hildreth operator didasarkan pada deteksi nol-penyeberangan dari operator Laplacian diterapkan ke merapikan Gauss-gambar. Dapat ditunjukkan, bagaimanapun, bahwa operator ini juga akan return false tepi sesuai dengan minima lokal dari besarnya gradien. Selain itu, operator ini akan memberikan lokalisasi miskin di tepi melengkung. Oleh karena itu, operator ini hari ini terutama dari kepentingan sejarah.
[sunting] Differential deteksi tepi

Yang lebih halus orde kedua pendekatan deteksi tepi, yang juga secara otomatis memberikan pinggirnya dengan sub-pixel akurasi, adalah dengan menggunakan pendekatan diferensial berikut mendeteksi nol-penyeberangan dari orde kedua arah gradien derivatif dalam arah: geometri diferensial Mengikuti cara mengungkapkan kebutuhan non-penekanan maksimum yang diusulkan oleh Lindeberg [9] [3], marilah kita memperkenalkan pada setiap gambar titik sistem koordinat lokal (u, v), dengan arah v sejajar dengan arah gradien. Dengan asumsi bahwa gambar telah presmoothed oleh Gaussian smoothing dan skala-ruang representasi L (x, y; t) pada t skala telah dihitung, kita dapat meminta bahwa gradien besarnya skala ruang-representasi, yang sama dengan orde pertama derivatif dalam arah-arah v Lv, harus mempunyai arah urutan pertama derivatif dalam arah v-sama dengan nol

\ partial_v (L_v) = 0

sedangkan orde kedua arah derivatif di v-arah harus Lv negatif, yaitu,

\ partial_ (vv) (L_v) \ leq 0.

Ditulis sebagai ekspresi eksplisit dalam hal derivatif parsial lokal Lx, Ly ... Lyyy, definisi tepi ini dapat dinyatakan sebagai nol-persimpangan diferensial kurva dari invarian

L_v ^ 2 ļ_ (vv) = L_x ^ 2 \, ļ_ (xx) + 2 \, L_x \, L_y \, ļ_ (xy) + L_y ^ 2 \, ļ_ (TH) = 0,

yang memenuhi tanda-kondisi di diferensial berikut invarian

L_v ^ 3 ļ_ (vvv) = L_x ^ 3 \, ļ_ (xxx) + 3 \, L_x ^ 2 \, L_y \, ļ_ (xxy) + 3 \, L_x \, L_y ^ 2 \, ļ_ (XYY) + L_y ^ 3 \, ļ_ (yyy) \ leq 0

dimana Lx, Ly ... Lyyy menunjukkan derivatif parsial dihitung dari skala-ruang representasi L diperoleh dengan merapikan gambar asli dengan sebuah kernel Gaussian. Dengan cara ini, ujung-ujungnya akan secara otomatis diperoleh sebagai kurva kontinu dengan akurasi subpixel. Histeresis thresholding juga dapat diterapkan untuk ini tepi subpixel diferensial dan segmen.

Dalam prakteknya, derivatif orde pertama perkiraan dapat dihitung dengan perbedaan pusat seperti dijelaskan di atas, sedangkan derivatif orde kedua dapat dihitung dari skala-ruang representasi L menurut:

Ļ_ (xx) (x, y) = L (x-1, y) - 2 L (x, y) + L (x +1, y). \,
Ļ_ (xy) (x, y) = (L (x-1, y-1) - L (x-1, y +1) - L (x +1, y-1) + L (x +1, y +1)) / 4, \,
Ļ_ (TH) (x, y) = L (x, y-1) - 2 L (x, y) + L (x, y +1). \,

sesuai dengan masker penyaring berikut:

Ļ_ (xx) = \ begin (bmatrix) 1 & -2 & 1 \ end (bmatrix) * L \ quad \ mbox (dan) \ quad ļ_ (xy) = \ begin (bmatrix) -1 / 4 & 0 & 1 / 4 \ \ 0 & 0 & 0 \ \ 1 / 4 & 0 & -1 / 4 \ end (bmatrix) * L \ quad \ mbox (dan) \ quad ļ_ (TH) = \ begin (bmatrix) 1 \ \ -2 \ \ 1 \ end (bmatrix) * L

Derivatif orde yang lebih tinggi untuk ketiga orde kondisi tanda dapat diperoleh dalam mode analog.
[sunting] Fase kesesuaian berdasarkan deteksi tepi

Sebuah perkembangan terbaru di tepi teknik deteksi domain frekuensi mengambil pendekatan untuk menemukan lokasi tepi. Fase kesesuaian (juga dikenal sebagai fase koherensi) metode berusaha untuk mencari lokasi dalam foto di mana semua sinusoid di frekuensi domain adalah dalam fase. Lokasi ini biasanya akan sesuai dengan lokasi tepi yang dirasakan, terlepas dari apakah tepi diwakili oleh perubahan besar dalam intensitas dalam domain spasial. Manfaat utama dari teknik ini adalah bahwa hal itu menanggapi Mach kuat untuk band, dan menghindari kesalahan positif biasanya ditemukan di sekitar tepi-tepi atap. Sebuah tepi atap, adalah sebuah diskontinuitas dalam urutan pertama turunan dari tingkat berwarna abu-abu profil. [10]
[sunting] Referensi

1. ^ HG Barrow dan JM Tenenbaum (1981) "garis Interpreting gambar tiga dimensi permukaan", Artificial Intelligence, jilid 17, hal 1-3, halaman 75-116.
2. ^ Ab T. Lindeberg (2001) "Edge deteksi", dalam M. Hazewinkel (editor), Encyclopedia of Mathematics, Kluwer / Springer, ISBN 1402006098.
3. ^ Abc T. Lindeberg (1998) "Edge deteksi dan punggung deteksi dengan skala otomatis pilihan", International Journal of Computer Vision, 30, 2, halaman 117-154.
4. ^ W. Zhang dan F. Bergholm (1997) "Multi-skala mengaburkan tepi estimasi dan klasifikasi untuk jenis analisis TKP", International Journal of Computer Vision, jilid 24, edisi 3, Halaman: 219-250.
5. ^ D. Ziou dan S. Tabbone (1998) "Edge teknik deteksi: An overview", International Journal of Pattern Recognition and Image Analisis, 8 (4) :537 - 559, 1998
6. ^ JM Park dan Y. Lu (2008) "Ujung deteksi di grayscale, warna, dan kisaran foto", di BW Wah (editor) Encyclopedia of Computer Science and Engineering, DOI 10.1002/9780470050118.ecse603
7. ^ J. lihai (1986) "Sebuah pendekatan komputasi deteksi tepi", IEEE Trans. Analisis pola dan Mesin Intelijen, jilid 8, halaman 679-714.
8. ^ R. Deriche (1987) Menggunakan kriteria cerdik untuk menurunkan detektor tepi yang optimal secara rekursif diterapkan, Int. J. Computer Vision, jilid 1, halaman 167-187.
9. ^ T. Lindeberg (1993) "derivatif Diskrit perkiraan dengan skala ruang-sifat: Sebuah dasar untuk tingkat rendah fitur ekstraksi", J. of Mathematical Imaging dan Visi, 3 (4), halaman 349-376.
10. ^ T. Pajdla dan V. Halvac (1993) "diskontinuitas dalam jangkauan permukaan gambar," dalam IEEE Proc 4 Int. Conf. Comput. Visi, hal. 524-528.