Algoritma Deteksi Garis Besar Gambar

Artikel ini menyajikan empat algoritma deteksi loop paling umum.

Dua yang pertama, yaitu algoritma untuk menelusuri kotak dan menelusuri lingkungan Moore, mudah diimplementasikan, dan oleh karena itu sering digunakan untuk menentukan kontur pola yang diberikan. Sayangnya, kedua algoritma memiliki beberapa kelemahan, yang membuatnya tidak mungkin untuk mendeteksi kontur kelas pola yang besar karena jenis kedekatan khusus mereka.

Algoritma ini akan mengabaikan semua "lubang" dalam pola. Sebagai contoh, jika kita memiliki pola yang mirip dengan yang ditunjukkan pada Gambar 1 , maka sirkuit yang dideteksi oleh algoritma akan serupa dengan yang ditunjukkan pada Gambar 2 (garis besar ditunjukkan oleh piksel biru). Di beberapa area aplikasi ini cukup dapat diterima, tetapi di area lain, misalnya, dalam pengenalan karakter, deteksi bagian internal suatu pola diperlukan untuk menemukan semua ruang yang membedakan karakter tertentu. ( Gambar 3 menunjukkan garis "penuh" dari pola.)



Oleh karena itu, untuk mendapatkan kontur lengkap, pertama-tama perlu menggunakan algoritma "pencarian lubang" yang menentukan lubang dalam pola yang diberikan, dan kemudian menerapkan algoritma deteksi kontur untuk setiap lubang.

Apa itu konektivitas?

Dalam gambar digital dengan nilai-nilai biner, sebuah piksel dapat memiliki salah satu dari nilai berikut: 1 - ketika itu merupakan bagian dari pola, atau 0 - ketika itu adalah bagian dari latar belakang, mis. tidak ada gradasi abu-abu. (Kami akan menganggap bahwa piksel dengan nilai 1 berwarna hitam, dan dengan nilai 0 berwarna putih).

Untuk mengidentifikasi objek dalam pola digital, kita perlu menemukan kelompok piksel hitam yang "terhubung" satu sama lain. Dengan kata lain, objek dalam pola digital yang diberikan adalah komponen yang terhubung dari pola ini.

Dalam kasus umum, komponen yang terhubung adalah sekumpulan piksel hitam P , sehingga untuk setiap pasangan piksel p _i dan p _j dalam P ada urutan piksel p _i , ..., p _j sedemikian rupa sehingga:

a) semua piksel dalam urutan berada di set P , mis. hitam, dan

b) setiap 2 piksel dalam urutan di samping satu sama lain adalah "tetangga".

Sebuah pertanyaan penting muncul: kapan kita dapat mengatakan bahwa 2 piksel adalah "tetangga"? Karena kami menggunakan piksel kuadrat, jawaban untuk pertanyaan sebelumnya tidak sepele karena alasan berikut: dalam persegi kuadrat, piksel memiliki tepi atau simpul yang sama, atau tidak memiliki kesamaan. Setiap piksel memiliki 8 piksel yang sama dengannya; piksel seperti itu membentuk "lingkungan Moore" dari piksel itu. Haruskah kita mempertimbangkan piksel "tetangga" yang hanya memiliki satu simpul umum? Atau untuk dianggap "tetangga", dua piksel harus memiliki keunggulan bersama?

Jadi ada dua jenis konektivitas, yaitu: 4-connectedness dan 8-connectness.

4-koneksi

Kapan kita dapat mengatakan bahwa satu set piksel hitam yang diberikan adalah 4-terhubung? Pertama, Anda perlu mendefinisikan konsep tetangga 4 (juga disebut tetangga langsung ):

Definisi 4-tetangga : Sebuah piksel Q adalah 4-tetangga dari piksel P yang diberikan jika Q dan P memiliki tepi yang sama. 4-tetangga piksel P (ditetapkan sebagai P2, P4, P6, dan P8 ) ditunjukkan pada Gambar 2 di bawah ini.


Definisi komponen yang terhubung 4 : himpunan piksel hitam P adalah komponen yang terhubung 4 jika untuk setiap pasangan piksel p _i dan p _j dalam P ada urutan piksel p _i , ..., p _j sedemikian rupa sehingga:

a) semua piksel dalam urutan berada di set P , mis. hitam, dan

b) setiap dua piksel yang berdekatan dalam urutan adalah 4 tetangga

Contoh 4 pola yang terhubung

Diagram di bawah ini menunjukkan contoh pola 4-terhubung:

8-koneksi

Kapan saya bisa mengatakan bahwa satu set piksel hitam yang terhubung 8 ? Pertama, kita perlu mendefinisikan konsep tetangga 8 (juga disebut tetangga tidak langsung ):

Definisi 8-tetangga : Sebuah piksel Q adalah 8-tetangga (atau hanya tetangga ) dari piksel P yang diberikan jika Q dan P memiliki tepi atau simpul yang sama. 8-tetangga dari piksel P yang diberikan membentuk lingkungan Moore dari piksel ini.

Definisi komponen yang terhubung 8 : himpunan piksel hitam P adalah komponen yang terhubung 8 (atau hanya komponen yang terhubung ) jika untuk setiap pasangan piksel p _i dan p _j di P ada urutan piksel p _i , ..., p _j sedemikian rupa sehingga :

a) semua piksel dalam urutan berada di set P , mis. hitam, dan

b) setiap dua piksel yang berdekatan dalam urutan ini adalah 8 tetangga

Catatan : semua pola 4-terhubung 8-terhubung, mis. Pola 4-terhubung adalah bagian dari banyak pola 8-terhubung. Di sisi lain, pola 8-terhubung mungkin tidak terhubung-4.

Contoh pola 8-linked

Diagram di bawah ini menunjukkan pola yang terhubung 8 tetapi tidak terhubung:

Contoh pola yang tidak terhubung:

Diagram di bawah ini menunjukkan contoh pola yang tidak terhubung-8, mis. terdiri dari lebih dari satu komponen yang terhubung (diagram menunjukkan tiga komponen yang terhubung):

Algoritma Jejak Persegi

Ide

Gagasan di balik algoritma penelusuran persegi sangat sederhana; ini dapat dikaitkan dengan fakta bahwa algoritma adalah salah satu upaya pertama untuk mendeteksi kontur pola biner.

Untuk memahami cara kerjanya, Anda perlu sedikit imajinasi ...

Misalkan kita memiliki pola digital, misalnya, sekelompok piksel hitam pada latar belakang piksel putih, mis. di grid; temukan piksel hitam dan nyatakan sebagai piksel " awal " kami. (Menemukan piksel " awal " dapat diimplementasikan dengan berbagai cara; kita akan mulai dari sudut kiri bawah kisi, kami akan memindai setiap kolom piksel dari bawah ke atas, dari kolom paling kiri ke paling kanan, sampai kami menemukan piksel hitam. Kami akan mendeklarasikannya sebagai " awal " ".)

Sekarang bayangkan Anda seorang ladybug yang berdiri di piksel awal , seperti yang ditunjukkan pada Gambar 1 di bawah ini. Untuk mendapatkan garis besar pola, Anda perlu melakukan hal berikut:

, , ,

, , ,

.

Pixel hitam yang Anda lingkari akan menjadi garis besar pola.


Aspek penting dari algoritma jejak kuadrat adalah "sense of direction". Beralih ke kiri dan kanan dilakukan relatif terhadap lokasi saat ini, yang tergantung pada bagaimana Anda mencapai piksel saat ini. Karena itu, untuk membuat gerakan yang benar, Anda perlu melacak arah Anda.

Algoritma

Berikut ini adalah deskripsi formal dari algoritma penelusuran kuadrat:

Input: tessellation kuadrat, T , berisi komponen P yang terhubung sel hitam.

Output: baris B (b ₁ , b ₂ , ..., b _k ) dari piksel batas, mis. kontur.

Mulai

• Tentukan B sebagai set kosong.
• Pindai sel T dari bawah ke atas dan kiri ke kanan hingga ditemukan piksel hitam s dari P.
• Masukkan s ke B.
• Jadikan piksel saat ini sebagai piksel awal.
• Belok kiri, mis. pergi ke piksel tetangga di sebelah kiri p .
• Perbarui p , mis. itu menjadi piksel saat ini.
• Sementara p tidak sama dengan s , jalankan
  
  Jika p piksel saat ini berwarna hitam
  
  • masukkan p ke B dan belok kiri (pergi ke piksel tetangga di sebelah kiri p ).
  • Perbarui p , mis. itu menjadi piksel saat ini.
  
  jika tidak
  
  • belok kanan (pergi ke piksel berikutnya di sebelah kanan p ).
  • Perbarui p , mis. itu menjadi piksel saat ini.
  
  Akhir dari siklus "Sampai jumpa"

Akhirnya

Catatan: konsep "kiri" dan "kanan" harus dianggap tidak berkenaan dengan halaman atau pembaca, tetapi sehubungan dengan arah entri ke dalam piksel "saat ini" selama pemindaian.

Demonstrasi

Berikut ini adalah demonstrasi animasi tentang bagaimana algoritme jejak kuadrat mendeteksi garis besar pola. Jangan lupa bahwa kepik bergerak dalam piksel; perhatikan bagaimana arahnya berubah ketika belok kiri dan kanan. Belok kiri dan kanan dilakukan relatif terhadap arah saat ini dalam suatu piksel, mis. orientasi kepik.

Analisis

Ternyata kemampuan algoritma jejak kuadrat sangat terbatas. Dia tidak dapat mendeteksi kontur pola keluarga besar yang sering muncul dalam aplikasi dunia nyata.

Hal ini terutama disebabkan oleh kenyataan bahwa rotasi kiri dan kanan tidak memperhitungkan piksel akun yang terletak “sepanjang
diagonal "dari piksel saat ini.

Mari kita lihat pola yang berbeda dengan konektivitas yang berbeda dan lihat mengapa algoritma kuadrat persegi gagal. Selain itu, kami akan mempelajari cara untuk meningkatkan kemampuan algoritme dan membuatnya bekerja bahkan dengan pola yang memiliki jenis konektivitas khusus.

Hentikan kriteria

Salah satu kelemahan dari algoritma adalah pilihan kriteria berhenti. Dengan kata lain, kapan algoritma berhenti dijalankan?

Dalam deskripsi asli algoritme jejak kuadrat, kondisi penyelesaian adalah untuk memukul piksel awal untuk kedua kalinya. Ternyata jika algoritma tergantung pada kriteria seperti itu, maka itu tidak akan dapat mendeteksi kontur dari keluarga besar pola.

Berikut ini adalah demo animasi yang menjelaskan bagaimana algoritme tidak dapat mendeteksi kontur pola yang tepat karena pemilihan kriteria berhenti buruk:


Seperti yang Anda lihat, meningkatkan kriteria penghentian bisa menjadi awal yang baik untuk meningkatkan kinerja algoritma secara keseluruhan. Ada dua alternatif efektif untuk kriteria penutupan yang ada:

a) Hentikan hanya dengan mengunjungi piksel awal n kali, di mana n setidaknya 2, ATAU

b) Berhenti setelah menekan piksel awal untuk kedua kalinya, sama seperti kita menekannya pada awalnya.

Kriteria ini diusulkan oleh Yakub Eliosoff , jadi kita akan menyebutnya kriteria untuk menghentikan Yakub .

Mengubah kriteria pemberhentian umumnya meningkatkan efektivitas algoritme jejak kuadrat, tetapi tidak memungkinkan untuk mengatasi kelemahan lain yang dimilikinya dalam hal pola dengan jenis konektivitas khusus.

Algoritma Square Tracing tidak dapat mendeteksi kontur pola keluarga dengan konektivitas 8 yang TIDAK memiliki konektivitas 4.

Berikut ini adalah demonstrasi animasi tentang bagaimana algoritme jejak kuadrat (dengan kriteria berhenti Jacob) gagal mendeteksi garis besar pola yang benar dengan konektivitas 8 tanpa konektivitas 4:

Apakah algoritma ini sama sekali tidak berguna?

Jika Anda membaca analisis di atas, Anda mungkin berpikir bahwa algoritme jejak kuadrat gagal mendeteksi garis besar sebagian besar pola. Tapi ternyata itu. bahwa ada keluarga khusus pola di mana jalur sepenuhnya terdeteksi oleh algoritma jejak kuadrat.

Misalkan P adalah himpunan piksel hitam dengan konektivitas 4 di grid. Biarkan piksel putih kotak, mis. piksel latar belakang W juga memiliki konektivitas 4. Ternyata dalam kondisi pola dan latar belakang seperti itu, dapat dibuktikan bahwa algoritme jejak kuadrat (dengan kriteria stop Jacob) akan selalu berhasil menangani penentuan kontur.

Di bawah ini adalah bukti bahwa dalam kasus di mana kedua pola dan piksel latar belakang terhubung, algoritma kuadrat persegi akan menentukan kontur dengan benar ketika menggunakan kriteria berhenti Jacob.

Bukti
Diberikan : pola P sedemikian rupa sehingga semua piksel pola (mis. Hitam) dan piksel latar belakang (mis. Putih) W memiliki konektivitas 4.

Pengamatan pertama

Karena himpunan piksel putih W memiliki konektivitas 4, ini berarti bahwa tidak ada " lubang " dalam pola (dalam istilah informal, " lubang " kami maksudkan kelompok piksel putih sepenuhnya dikelilingi oleh piksel hitam dari pola).

Kehadiran " lubang " dalam pola akan mengarah pada pemisahan kelompok piksel putih dari piksel putih yang tersisa; namun, banyak piksel putih kehilangan konektivitas 4.

Gambar 2 dan Gambar 3 di bawah ini menunjukkan dua jenis " lubang " yang dapat terjadi dalam suatu pola dengan konektivitas 4:



Pengamatan kedua

Dua piksel hitam dari suatu pola HARUS memiliki satu sisi yang sama.

Misalkan dua piksel hitam hanya memiliki satu simpul umum. Kemudian, untuk memenuhi sifat 4-keterhubungan pola, harus ada jalur yang menghubungkan dua piksel ini sehingga setiap dua piksel yang berdekatan di jalur ini memiliki konektivitas 4. Tetapi ini akan memberi kita pola yang mirip dengan Gambar 3 . Dengan kata lain, ini akan menghasilkan pemisahan piksel putih. Gambar 4 di bawah ini menunjukkan pola khas yang memuaskan asumsi bahwa piksel dalam pola dan latar belakang 4-terhubung, mis. tidak memiliki " lubang ", dan setiap dua piksel hitam memiliki satu sisi yang sama:


Berguna untuk mewakili pola-pola seperti berikut:

Pertama-tama kita mempertimbangkan piksel batas, mis. garis besar polanya. Kemudian, jika kita menganggap setiap piksel batas memiliki 4 tepi panjang unit, kita akan melihat bahwa beberapa tepi ini sama dengan piksel putih tetangga. Kami akan memanggil tepi batas seperti tepi .

Tepi batas seperti itu dapat dianggap sebagai tepi poligon. Dalam gambar
5 di bawah, ide ini ditunjukkan oleh contoh poligon yang sesuai dengan pola dari Gambar 4 di atas:


Jika kita mempertimbangkan semua "konfigurasi" piksel batas yang mungkin terjadi dalam pola seperti itu, kita akan melihat bahwa ada dua kasus sederhana, yang ditunjukkan pada Gambar 6 dan Gambar 7 di bawah ini.

Piksel batas dapat merupakan kelipatan dari kasus ini atau pengaturan lainnya, mis. liku-liku dari dua kasus ini. Rusuk batas ditandai dengan warna biru sebagai E1, E2, E3 dan E4 .


Pengamatan ketiga

Dalam kasus dua kasus di atas, tidak peduli berapa piksel awal yang kita pilih, dan ke arah mana pun jatuh ke dalamnya, algoritma jejak persegi tidak akan pernah "kembali" (mundur) , itu tidak akan pernah "melewati" batas tepi dua kali ( hanya jika tidak melacak perbatasan untuk kedua kalinya) dan jangan pernah melewatkan batas tepi . Lihat itu!

Dua konsep perlu diklarifikasi di sini:

a) algoritma "kembali" , ketika sebelum menelusuri seluruh perbatasan, kembali untuk mengunjungi piksel yang sudah dikunjungi, dan

b) untuk setiap tulang rusuk batas, ada dua cara untuk "melewatinya" , yaitu "ke dalam" dan "ke luar" (di mana "ke dalam" berarti pergerakan ke dalam dari poligon yang sesuai, dan "ke luar" - ke luar dari poligon).

Selain itu, ketika algoritma melewati "ke dalam" melalui salah satu tepi batas, itu akan melewati "ke luar" melalui tepi batas berikutnya, mis. algoritme penelusuran kuadrat seharusnya tidak dapat melewati dua sisi berurutan dengan cara yang sama.

Pengamatan terakhir

Setiap pola memiliki jumlah tepi batas genap .

Jika Anda melihat poligon dari Gambar 5 , Anda dapat melihat bahwa:

jika kita ingin memulai dari titik S yang ditandai dalam diagram dan mengikuti batas tepi sampai kita mencapai S lagi, maka kita perhatikan bahwa dalam proses kita melewati sejumlah tepi batas genap. Kita dapat menganggap setiap batas batas sebagai "langkah" dalam arah yang terpisah. Kemudian untuk setiap "langkah" ke kanan harus ada "langkah" yang sesuai ke kiri, jika kita ingin kembali ke posisi awal. Hal yang sama berlaku untuk "langkah" vertikal. Oleh karena itu, "langkah-langkah" harus memiliki pasangan yang sesuai, dan ini menjelaskan mengapa masing-masing pola ini akan memiliki jumlah tepi batas genap.

Oleh karena itu, ketika algoritma untuk melacak kotak masuk melalui batas batas awal (dari piksel awal) untuk kedua kalinya, maka ia akan melakukannya dengan arah yang sama dengan yang pertama kali.

Alasan untuk ini adalah karena ada dua cara untuk pergi melalui batas tepi, dan algoritma bergantian bergerak ke dalam dan ke luar, dan ada sejumlah tepi batas, algoritma akan melalui tepi batas awal untuk kedua kalinya dengan cara yang sama seperti di yang pertama.

Kesimpulan

Dalam kasus pola dan latar belakang yang terhubung 4, algoritme jejak kuadrat akan mendeteksi seluruh perbatasan, mis. kontur, pola, dan akan berhenti bekerja setelah satu jejak, yaitu itu tidak akan melacaknya lagi, karena ketika mencapai batas batas awal untuk kedua kalinya, itu akan masuk dengan cara yang sama seperti pertama kali. Oleh karena itu, algoritme jejak kuadrat dengan kriteria stop Jacob akan dengan benar menentukan penghitung pola apa pun, asalkan pola dan latar belakangnya terhubung 4.

Menelusuri lingkungan Moore

Ide

Gagasan di balik penelusuran Moore-Tetangga itu sederhana; tetapi sebelum menjelaskannya, kita perlu menjelaskan konsep penting: lingkungan Moore dari sebuah piksel.

Lingkungan Moore

Lingkungan Moore dari piksel P adalah satu set 8 piksel yang memiliki simpul atau tepi yang sama dengan piksel tersebut. Pixel tersebut, yaitu P1, P2, P3, P4, P5, P6, P7 dan P8 , ditunjukkan pada Gambar 1 .

Lingkungan Moore (juga disebut 8-tetangga atau tetangga tidak langsung ) adalah konsep penting yang sering disebut dalam literatur.


Sekarang kita siap untuk berkenalan dengan ide yang mendasari jejak lingkungan Moore.

Biarkan ada pola digital, mis. sekelompok piksel hitam, dengan latar belakang piksel putih, mis. di grid; temukan piksel hitam dan nyatakan sebagai piksel " awal ". (Ada beberapa cara untuk menemukan piksel " awal ", tetapi kami, seperti sebelumnya, akan mulai dari sudut kiri bawah dan memindai semua kolom piksel secara berurutan, hingga kami menemukan piksel hitam pertama, yang akan kami nyatakan sebagai " awal ".)

Sekarang lagi, bayangkan Anda seorang ladybug yang berdiri di piksel awal , seperti yang ditunjukkan pada Gambar 2 di bawah ini. Tanpa kehilangan generalisasi, kami akan mendeteksi garis besar dengan bergerak di sekitar pola searah jarum jam. (Tidak peduli arah mana yang kita pilih, hal utama adalah menggunakannya secara konstan dalam algoritma).

Gagasan umumnya adalah ini: setiap kali kita sampai pada piksel hitam P , kita kembali, yaitu ke piksel putih tempat kita berdiri sebelumnya. Lalu kita berkeliling pixel P searah jarum jam, mengunjungi setiap piksel di sekitar Moore, sampai kita sampai ke piksel hitam. Algoritma berakhir ketika piksel awal mencapai piksel awal untuk kedua kalinya.

Piksel hitam yang dikunjungi algoritma akan menjadi garis besar pola.

Algoritma

Berikut ini adalah deskripsi formal dari algoritma penelusuran lingkungan Moore:

Input: tessellation kuadrat T yang mengandung komponen P sel-sel hitam yang terhubung.

Output: baris B (b ₁ , b ₂ , ..., b _k ) dari piksel batas, mis. kontur.

Ditunjukkan oleh M (a) lingkungan Moore dari pixel a .

Biarkan p menjadi piksel batas saat ini.

Biarkan c menjadi piksel saat ini dalam pertimbangan, mis. c ada di M (p) .

Mulai

• Tentukan B sebagai set kosong.
• Dari bawah ke atas dan dari kiri ke kanan, pindai sel T hingga kami menemukan piksel hitam s dari P.
• Masukkan s ke B.
• Kami menetapkan titik s sebagai titik batas p saat ini, mis. p = s
• Ayo kembali, mis. mari kita beralih ke pixel dari mana kita sampai.
• Biarkan c menjadi piksel searah jarum jam berikutnya dalam M (p) .
• Sementara c tidak sama dengan s , jalankan
  
  
  • jika c berwarna hitam
    
    • Masukkan c ke B
    • kita atur p = c
    • kembali (pindahkan piksel saat ini c ke piksel dari mana kita harus p )
    
    jika tidak
    
    • pindahkan piksel saat ini c ke piksel searah jarum jam berikutnya dalam M (p)
    
    Akhir Siklus Dah

Akhirnya

Demonstrasi

Berikut ini adalah demonstrasi animasi tentang bagaimana jejak lingkungan Moore melakukan deteksi pola garis besar. (Kami memutuskan untuk melacak garis searah jarum jam.)

Analisis

Kelemahan utama dalam melacak lingkungan Moore terletak pada pilihan kriteria berhenti.

Dalam uraian asli algoritma untuk melacak lingkungan Moore, kriteria berhenti adalah untuk memukul piksel awal untuk kedua kalinya. Mirip dengan algoritma penelusuran persegi, ternyata menelusuri lingkungan Moore menggunakan kriteria ini tidak dapat mendeteksi kontur pola keluarga besar.

Berikut ini adalah demo animasi yang menjelaskan mengapa algoritme tidak dapat menemukan garis besar pola yang tepat karena pemilihan kriteria berhenti buruk:


Seperti yang Anda lihat, meningkatkan kriteria penghentian bisa menjadi awal yang baik untuk meningkatkan kinerja keseluruhan jejak. Ada dua alternatif efektif untuk kriteria penutupan, mirip dengan kriteria penutupan Yakub.

Menggunakan kriteria Jacob secara signifikan meningkatkan efektivitas penelusuran lingkungan Moore, menjadikannya algoritma terbaik untuk menentukan kontur pola apa pun, terlepas dari konektivitasnya.

Alasan untuk ini terutama karena algoritma memeriksa seluruh lingkungan Moore dari piksel batas untuk mencari piksel batas berikutnya. Berbeda dengan algoritma penelusuran kuadrat, yang hanya berputar ke kiri dan ke kanan dan melewatkan piksel “secara diagonal,” penelusuran lingkungan Moore akan selalu dapat mendeteksi batas luar komponen yang terhubung. Alasannya adalah ini: untuk pola 8-terhubung (atau hanya terhubung ), pixel perbatasan berikutnya terletak di dalam lingkungan Moore dari pixel perbatasan saat ini. Karena penelusuran lingkungan Moore memeriksa masing-masing piksel di lingkungan Moore dari piksel batas saat ini, ia harus mendeteksi piksel batas berikutnya.

Ketika penelusuran lingkungan Moore mencapai piksel awal untuk kedua kalinya dengan cara yang sama seperti yang ia lakukan pertama kali, ini berarti bahwa kontur eksternal lengkap dari pola telah terdeteksi, dan jika algoritme tidak dihentikan, ia akan kembali mendeteksi kontur yang sama.

Pemindaian radial

Radial Sweep Algorithm adalah algoritma pendeteksian kontur yang dibahas dalam beberapa buku. Terlepas dari nama yang rumit, ide yang mendasarinya sangat sederhana. Bahkan, ternyata algoritma sapuan radial identik dengan jejak lingkungan Moore. Seseorang mungkin bertanya: "Mengapa kita menyebutkannya?"

Menelusuri lingkungan Moore mencari di sekitar Moore untuk pixel batas saat ini dalam arah tertentu (kami memilih arah searah jarum jam) sampai menemukan pixel hitam. Dia kemudian menyatakan piksel itu sebagai piksel batas saat ini dan berlanjut.

Algoritma pemindaian radial melakukan hal yang sama. Di sisi lain, ini menyediakan cara yang menarik untuk menemukan piksel hitam berikutnya di lingkungan Moore dari piksel batas yang diberikan.

Metode ini didasarkan pada gagasan berikut:

setiap kali kami menemukan piksel batas baru, jadikan itu piksel P saat ini, dan gambar segmen garis imajiner yang menghubungkan P dengan piksel batas sebelumnya . Lalu kami memutar segmen relatif ke P searah jarum jam hingga muncul piksel hitam di lingkungan Moore dari piksel P. Rotasi garis identik dengan memeriksa setiap piksel di sekitar Moore P.

Kami membuat demonstrasi animasi tentang bagaimana algoritma pemindaian radial bekerja dan bagaimana tampilannya menelusuri lingkungan Moore.


Dan kapan algoritma sapuan radial berhenti?

Mari kita jelaskan perilaku algoritma menggunakan kriteria berhenti berikut ...

Hentikan kriteria 1

Biarkan algoritma pemindaian radial selesai ketika mengunjungi piksel awal untuk kedua kalinya.

Di bawah ini adalah demo animasi, yang jelas mengapa kriteria break akan diubah dengan benar.


Perlu juga disebutkan bahwa ketika menggunakan kriteria berhenti ini di kedua algoritma, efektivitas algoritma pemindaian radial identik dengan penelusuran lingkungan Moore.

Dalam algoritma penelusuran kuadrat dan penelusuran lingkungan Moore, kami menemukan bahwa menggunakan kriteria berhenti Jacob secara signifikan meningkatkan kinerja kedua algoritma.

Kriteria berhenti Jacob mengharuskan algoritma untuk berhenti mengeksekusi ketika mengunjungi pixel awal untuk kedua kalinya dalam arah yang sama dengan yang pertama kali.

Sayangnya, kami tidak dapat menggunakan kriteria stop Jacob dalam algoritme sapuan radial. Alasannya adalah bahwa algoritma pemindaian radial tidak mendefinisikan konsep"Arah" di mana ia menyentuh piksel batas . Dengan kata lain, tidak jelas "arah" di mana algoritma jatuh ke piksel batas (dan definisinya adalah nontrivial).

Oleh karena itu, kita perlu mengusulkan kriteria penghentian lain, yang tidak tergantung pada arah memukul piksel tertentu, yang dapat meningkatkan efektivitas algoritma pemindaian radial ...

Hentikan kriteria 2

Misalkan setiap kali algoritme mendeteksi piksel batas baru P _i , dimasukkan ke dalam serangkaian piksel batas: P ₁ , P ₂ , P ₃ , ..., P _i ; dan dinyatakan sebagai piksel batas saat ini. ( P ₁ kami akan mempertimbangkan piksel awal ). Ini berarti bahwa kita mengetahui batas piksel P _{i-1 sebelumnya dari} setiap piksel batas P _{i saat ini} . (Adapun piksel awal , kami akan menganggap bahwa P ₀adalah piksel imajiner yang tidak sepadan dengan piksel di grid yang menghadap piksel awal di deretan piksel batas).

Mengingat asumsi di atas, kita dapat menentukan kriteria berhenti sebagai berikut:

Algoritma berakhir eksekusi ketika:

a) arus batas pixel P _i telah sebelumnya bertemu sebagai pixel P _j (di mana j <i ) dalam rangkaian piksel batas, dan

b) P _{i- 1} = P _j-1 .

Dengan kata lain, algoritma menyelesaikan eksekusi ketika mengunjungi batas pixel P pada detiklagi, jika pixel batas untuk P (dalam serangkaian piksel batas) di kedua kalinya adalah sama pixel yang ke P, ketika P dikunjungi oleh pertama kalinya.

Jika kondisi kriteria stop terpenuhi dan algoritme tidak dimatikan, maka algoritme pemindaian radial akan terus mendeteksi batas yang sama untuk kedua kalinya.

Kinerja algoritme sapuan radial dengan kriteria penghentian ini mirip dengan kinerja penelusuran lingkungan Moore dengan kriteria penghentian Jacob.

Algoritma Theo Pavlidis

Ide

Algoritma ini adalah salah satu algoritma deteksi loop terbaru yang diusulkan oleh Theo Pavlidis . Dia mengutipnya dalam bukunya tahun 1982 Algoritma untuk Grafis dan Pemrosesan Gambar (bab 7, bagian 5). Ini tidak sesederhana algoritma untuk menelusuri kotak atau menelusuri lingkungan Moore, tetapi tidak begitu rumit (ini khas untuk kebanyakan algoritma deteksi tepi).

Kami tidak akan menjelaskan algoritma ini dengan cara yang sama seperti yang dilakukan dalam bukunya. Pendekatan kami lebih mudah dipahami dan memberikan gagasan tentang ide umum yang mendasari algoritma.

Tanpa kehilangan generalisasi, kami memutuskan untuk memutar loop searah jarum jam untuk mencocokkan urutan semua algoritma lain yang disajikan dalam artikel. Di sisi lain, Pavlidis memilih arah berlawanan arah jarum jam. Ini tidak akan mempengaruhi kinerja algoritma. Satu-satunya perbedaan adalah arah relatif dari gerakan yang akan kita lakukan ketika kita mengelilingi kontur.

Sekarang mari kita beralih ke ide ...

Katakanlah kita memiliki pola digital, yaitu sekelompok piksel hitam pada latar belakang piksel putih, mis. di grid; temukan piksel hitam dan nyatakan sebagai piksel " awal ". Anda dapat mencari piksel " awal " dengan berbagai cara, misalnya, seperti dijelaskan di atas.

Untuk menemukan inisialpiksel untuk menggunakan metode ini adalah opsional. Sebagai gantinya, kami akan memilih piksel awal yang memenuhi batasan berikut yang diberlakukan oleh algoritma Pavlidis untuk memilih piksel awal:

Batasan penting dari arah masuknya piksel awal.

Faktanya, Anda dapat memilih SETIAP piksel perbatasan hitam sebagai piksel awal dalam kondisi ini: jika Anda awalnya berdiri di atasnya, piksel tetangga sebelah kiri TIDAK hitam. Dengan kata lain, Anda harus memasukkan piksel awal sedemikian rupa sehingga piksel tetangga sebelahnya berwarna putih ("kiri" di sini diambil relatif terhadap arah masuknya piksel awal ).

Sekarang bayangkan Anda seorang ladybug berdirimulai pixel, seperti yang ditunjukkan pada Gambar 1 di bawah ini. Selama eksekusi algoritme, kami hanya akan tertarik pada tiga piksel di depan Anda, mis. P1, P2 dan P3 ditunjukkan pada Gambar 1 . (Kami akan menetapkan P2 sebagai piksel di depan Anda, P1 adalah piksel di sebelah kiri P2 , dan P3 adalah piksel di sebelah kanan P2 ).


Seperti halnya dengan algoritma jejak kuadrat, hal terpenting dalam algoritma Pavlidis adalah “sense of direction”. Belok kiri dan kanan relatif terhadap posisi saat ini, yang tergantung pada bagaimana Anda memasukkan piksel saat ini. Karena itu, untuk membuat gerakan yang benar, penting untuk melacak orientasi Anda saat ini. Tetapi tidak peduli bagaimana Anda berada, piksel P1, P2 dan P3 ditentukan seperti yang dijelaskan di atas.

Dengan informasi ini, kami siap menjelaskan algoritme ...

Setiap kali Anda berdiri di piksel batas saat ini (yang merupakan piksel awal ), kami melakukan yang berikut:

Pertama , periksa piksel P1 . Jika P1 berwarna hitam, maka nyatakan P1pixel batas saat ini dan bergerak satu langkah maju, dan kemudian mengambil langkah ke kiri untuk berada di P1 ( urutan gerakan sangat penting).

Dalam Gambar 2 di bawah ini menggambarkan hal ini. Jalur menuju ke P1 ditunjukkan dengan warna biru.


Dan hanya jika P1 berwarna putih, pergi untuk memeriksa P2 ...

Jika P2 berwarna hitam, maka mendeklarasikan P2 piksel batas saat ini dan bergerak satu langkah maju untuk berada pada P2 . Kasus ini ditunjukkan pada Gambar 3 di bawah ini. Jalur yang harus Anda ikuti pada P2 ditunjukkan dengan warna biru.


Hanya jika P1 dan P2 berwarna putih, buka untuk memeriksa P3 ...

Jika P3 berwarna hitam, maka nyatakan P3 piksel batas saat ini dan gerakkan satu langkah ke kanan, lalu satu langkah ke kiri , seperti yang ditunjukkan pada Gambar 4 di bawah ini.


Itu saja! Tiga aturan sederhana untuk tiga kasus sederhana. Seperti yang Anda lihat, penting untuk melacak arah Anda saat menikung, karena semua gerakan dibuat relatif terhadap orientasi saat ini. Tapi sepertinya kita lupa sesuatu? Bagaimana jika ketiga piksel putih di depan kita? Kemudian kita memutar (berdiri di piksel batas saat ini) 90 derajat searah jarum jam untuk melihat set baru tiga piksel di depan kita. Kemudian kami melakukan pemeriksaan yang sama untuk piksel baru ini. Anda mungkin masih tetap pertanyaan: Bagaimana jika semua ini tiga piksel akan menjadi putih?! Kemudian lagi kita putar 90 derajat searah jarum jam, berdiri pada piksel yang sama. Sebelum Anda memeriksa seluruh lingkungan piksel Moore, Anda dapat memutar tiga kali (setiap kali 90 derajat searah jarum jam).

Jika kita memutar tiga kali tanpa pernah menemukan piksel hitam, maka ini berarti kita berdiri pada piksel yang terisolasi , tidak terhubung ke piksel hitam lainnya. Itulah sebabnya algoritma memungkinkan Anda untuk memutar tiga kali, dan kemudian menyelesaikan eksekusi.

Aspek lain: Kapan algoritma menyelesaikan eksekusi?

Algoritma berakhir dalam dua kasus:

a) seperti yang disebutkan di atas. algoritme memungkinkan Anda untuk memutar tiga kali (90 derajat searah jarum jam setiap kali), setelah menyelesaikan eksekusi dan mendeklarasikan piksel yang terisolasi ATAU

b) ketika piksel batas saat ini adalah piksel awal , algoritme menyelesaikan eksekusi dengan "menyatakan" bahwa ia mendeteksi garis besar pola.

Algoritma

Berikut ini adalah deskripsi formal dari algoritma Pavlidis:

Input: square tessellation T yang mengandung komponen P yang terhubung sel hitam.

Output: baris B (b ₁ , b ₂ , ..., b _k ) dari piksel batas, mis. kontur.

Definisi:

• Ditunjukkan oleh p batas piksel saat ini, mis. piksel tempat kami berdiri.
• Tetapkan P1, P2, dan P3 sebagai berikut: (lihat juga Gambar 1 di atas)
• P2 adalah piksel di depan Anda, bersebelahan dengan piksel tempat Anda berdiri, mis. dengan piksel p .
• P1 — , P2 .
• P3 — , P2 .
• «» .

Mulai

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • menghentikan program dan mendeklarasikan p piksel yang terisolasi
  
  jika tidak
  
  • putar 90 derajat searah jarum jam, berdiri di p piksel saat ini
  
  Sejauh ini p = s (Akhiri loop berulang)

Akhirnya

Demonstrasi

Berikut ini adalah demonstrasi animasi tentang bagaimana algoritma Pavlidis mendeteksi kontur dari pola yang diberikan. Jangan lupa bahwa kami berjalan dalam piksel; perhatikan bagaimana orientasi berubah ketika belok kiri atau kanan. Untuk menjelaskan algoritme sedetail mungkin, kami menyertakan semua kasus yang mungkin ada di dalamnya.

Analisis

Jika Anda berpikir bahwa algoritma Pavlidis ideal untuk mendeteksi garis pola, maka Anda harus berubah pikiran ...

Algoritma ini benar-benar sedikit lebih rumit daripada, misalnya, menelusuri lingkungan Moore, di mana tidak ada kasus khusus yang memerlukan pemrosesan terpisah, tetapi tidak akan dapat menentukan garis besar dari besar keluarga pola yang memiliki jenis konektivitas tertentu.

Algoritma bekerja dengan sangat baik pada pola 4-terhubung. Masalahnya terjadi ketika melacak beberapa pola 8-terhubung yang tidak 4-terhubung. Berikut ini adalah demonstrasi animasi tentang bagaimana algoritma Pavlidis gagal mendeteksi garis yang benar dari pola 8-terhubung (bukan 4-terhubung) - ia melompati sebagian besar perbatasan.


Ada dua cara sederhana untuk memodifikasi suatu algoritma untuk secara signifikan meningkatkan kinerjanya.

a) Ganti kriteria berhenti

Alih-alih menyelesaikan algoritme saat mengunjungi piksel awal untuk kedua kalinya, Anda dapat mengakhirinya saat mengunjungi piksel awal untuk ketiga atau bahkan keempat kalinya. Ini akan meningkatkan kinerja keseluruhan algoritma.

ATAU

b) Dapatkan ke sumber masalah, yaitu, sebelum memilih piksel awal.Ada

batasan penting mengenai arah di mana entri ke piksel awal dilakukan. Pada dasarnya, Anda perlu memasukkan piksel awal sehingga ketika Anda berdiri di atasnya, piksel di sebelah kiri Anda berwarna putih. Alasan untuk memperkenalkan pembatasan ini adalah ini: karena kami selalu melihat tiga piksel di depan kami padadalam urutan tertentu , dalam beberapa pola kita akan melewati piksel batas yang terletak langsung di sebelah kiri piksel awal.

Kami berisiko kehilangan tidak hanya piksel tetangga sebelah kiri dari piksel awal, tetapi juga piksel tepat di bawahnya (seperti yang ditunjukkan dalam analisis). Selain itu, dalam beberapa pola, piksel yang sesuai dengan piksel R pada Gambar 5 di bawah ini akan dilewati . Oleh karena itu, kami mengasumsikan bahwa piksel awal perlu dipukul sedemikian rupa sehingga piksel yang sesuai dengan piksel L, W dan R yang ditunjukkan pada Gambar 5 di bawah ini berwarna putih.


Dalam hal ini, pola-pola seperti yang ditunjukkan pada demonstrasi akan dideteksi dengan benar dan efektivitas algoritma Pavlidis akan meningkat secara signifikan. Di sisi lain, menemukan piksel awal yang memenuhi persyaratan ini dapat menjadi tantangan, dan dalam banyak kasus tidak mungkin menemukan piksel tersebut. Dalam hal ini, Anda harus menggunakan cara alternatif untuk meningkatkan algoritma Pavlidis, yaitu penyelesaian algoritma setelah mengunjungi titik awal untuk ketiga kalinya.