Pemotongan Otomatis Bentuk Sewenang-wenang

Saya memiliki bentuk arbitrer yang ditentukan oleh topeng biner (abu-abu = bentuk, hitam = latar belakang).

Saya ingin mencari persegi panjang terbesar yang mungkin hanya berisi piksel abu-abu (persegi panjang tersebut digambarkan dengan warna kuning):

Bentuk selalu "satu bagian" tetapi tidak harus cembung (tidak semua pasangan titik pada batas bentuk dapat dihubungkan oleh garis lurus melalui bentuk).

Kadang-kadang banyak "persegi panjang maksimum" seperti itu ada dan kemudian batasan lebih lanjut dapat diperkenalkan, seperti:

• Mengambil persegi panjang dengan pusatnya yang terdekat dengan pusat massa bentuk (atau pusat gambar)
• Mengambil persegi panjang dengan aspek rasio terdekat dengan rasio yang telah ditentukan (yaitu 4: 3)

Pikiran pertama saya tentang algoritma adalah sebagai berikut:

1. Hitung transformasi jarak bentuk dan temukan pusat massanya
2. Tumbuhkan area persegi sementara itu hanya berisi piksel bentuk
3. Tumbuhkan persegi panjang (awalnya persegi) dengan lebar atau tinggi sementara hanya berisi piksel bentuk.

Namun, saya pikir algoritma seperti itu akan lambat dan tidak akan mengarah pada solusi optimal.

Ada saran?

Ada kode pada Matlab Fileexchange yang relevan dengan masalah Anda: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscriptionReignangle/content/html/Inscribed_Rectangle_demo.html

Memperbarui

Saya menulis artikel tutorial ini tentang menghitung persegi panjang bertuliskan terbesar berdasarkan tautan di atas dari Atul Ingle.

Algoritma pertama mencari kotak terbesar pada topeng biner. Ini dilakukan dengan menggunakan algoritma pemrograman dinamis sederhana. Setiap piksel baru diperbarui menggunakan tiga tetangga yang sudah dikenal:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

Contoh topeng biner dan peta yang dihitung terlihat seperti ini:

Mengambil maksimum di peta mengungkapkan kotak tertulis terbesar:

Algoritme pencarian persegi panjang daripada memindai topeng dua kali lagi mencari dua kelas persegi panjang:

• lebar lebih besar dari ukuran kotak (dan tinggi mungkin lebih kecil)
• tinggi lebih besar dari ukuran persegi (dan lebar mungkin lebih kecil)

Kedua kelas dibatasi oleh kuadrat terbesar karena tidak ada persegi panjang pada titik tertentu dapat memiliki kedua dimensi lebih besar dari kuadrat tertulis (meskipun satu dimensi dapat lebih besar).

Kita harus memilih beberapa metrik untuk ukuran persegi panjang, seperti luas, keliling atau jumlah dimensi tertimbang.

Berikut adalah peta yang dihasilkan untuk persegi panjang:

Lebih mudah untuk menyimpan posisi dan ukuran persegi panjang terbaik yang ditemukan sejauh ini dalam sebuah variabel daripada membangun peta dan kemudian mencari maxima.

Aplikasi praktis dari algoritma ini adalah memotong gambar non-persegi panjang. Saya telah menggunakan algoritme ini di pustaka jahitan gambar saya SharpStitch :