Dijital üçgen tanıma örneği. Bitmap, iki boyutlu bir veri dizisi olarak bir görüntüdür. Modelin bilgisayarda görüntülenmesi
UDC 004932:621.396
T.M. VLASOVA, V.G. KALMIKOV
DİJİTAL HATLARIN BÖLÜMLERİNİN BİR DİZİ OLARAK GÖRÜNTÜ KONTURLARININ TANINMASI İÇİN ALGORİTMA VE PROGRAM
Özet: Verilen çalışmada, ikili görüntülerin konturlarında sayısal doğrudan doğru parçasının tanınması algoritması ve algoritmanın yazılım uygulaması ele alınmıştır. Görüntüleri işlemek için bu algoritmanın kullanılması, görüntülerin tarif edilmesinin bilinen yollarına kıyasla daha doğal ve ekonomik bir açıklama ile sonuçlanacaktır. İncelenen algoritma ve yazılım uygulaması, yarı tonlu ve renkli görüntüler işlenirken konturların tanımlanması için de kullanılabilir.
Anahtar kelimeler: görüntü, kontur, sayısal düz parçalar, algoritma, program.
Açıklama: Bu robotta, ikili görüntülerin konturlarındaki dijital çizgileri tanımak için bir algoritma ve algoritmanın bir yazılım uygulaması tanıtılmaktadır. Görüntünün tanımı, görüntünün kodlama yöntemlerine daha doğal ve ekonomik olarak eşit olacağı ölçüde görüntüyü işlemek için algoritma geliştirdik. Navtone ve renkli görüntüleri işlerken konturları kodlamak için önerilen algoritma ve yazılım uygulaması kurulabilir. Anahtar kelimeler: görüntüler, kontur, sayısal düz çizgiler, algoritma, program.
Özet: Bu yazıda, ikili görüntülerin konturlarındaki sayısal çizgilerin parçalarını tanımaya yönelik bir algoritma ve algoritmanın yazılım uygulaması ele alınmaktadır. Bu algoritmanın görüntü işlemede kullanılması, algoritmaya göre daha doğal ve ekonomik sonuç verecektir. bilinen yollar görüntülerin açıklaması. Dikkate alınan algoritma ve yazılım uygulaması, gri tonlamalı ve renkli görüntülerin işlenmesinde konturları tanımlamak için de kullanılabilir. anahtar kelimeler: görüntü, kontur, dijital çizgilerin segmentleri, algoritma, program.
1. Giriş
Düz çizgi parçaları ve eğri yaylarının dizileri olarak görüntü konturlarının yapısal analizi, yapay zeka sistemlerinde yorumlanması amacıyla görüntü işlemedeki ana görevlerden biridir.
Çoğu durumda, görüntü, görüntünün arka planını ve nesnelerini belirleyen optik yoğunluk, renk, doku gibi bazı yasalara göre sabit veya değişen parametrelere sahip alanlara bölünmüş düzlemin bir parçası olarak kabul edilebilir. Bu alanların her birinin ayrılmaz bir özelliği sınırıdır, yani kontur, çizgi parçalarından ve kavisli yaylardan oluşan basit bağlantılı bir dizidir. Bir raster görüntüyü işlerken, nesnelerin dış hatları genellikle vurgulanır. Bununla birlikte, bir dizi ayrı sınır pikseli olarak sunulan nesnelerin konturları, geometrik özünü yeterince ifade etmedikleri için daha sonraki işlemler için çok uygun değildir.
Bir dizi çizgi parçası şeklinde görüntü konturlarının tanınması, bir raster görüntünün işlenmesi sürecindeki ana görevlerden biri olarak kabul edilebilir. Bir konturu düz çizgi segmentlerinin bir dizisi olarak temsil etme problemini çözmek, görüntünün, insan algısı için doğal, afin dönüşümler altında değişmez, özellikle sinir ağları tarafından işlenmesi için uygun, kompakt bir biçimde bir tanımını elde etmeyi mümkün kılar. Çizgi parçaları, bir konturun temel öğeleridir. Bir eğrinin yayı da, hem kalkülüsün temellerinde hem de matematikte yazılı olan kesikli bir çizgi ile değiştirilir. çok sayıda pratik uygulamalar.
Bilinen yöntemler ve algoritmalar, özellikle çalışmada önerilenler, tüm uygulamalar için kabul edilemez olan yaklaşık bir çözüm elde etmeyi mümkün kılar.
Bu yazıda, ikili bir görüntünün konturunun tanınmasını, bilgi kaybı olmaksızın dijital düz çizgilerin bir dizi segmenti olarak ele alıyoruz.
2. Dijital çizgilerin bir dizi segmenti olarak kontur
AT bu bölüm görüntü konturlarının yapısal analizi, konturu dijital eğrilerin yaylarına ve dijital çizgilerin bölümlerine bölmek için ilk veriler olan bir dizi dijital çizgi segmenti olarak kabul edilir.
Nesneleri tamamen sınırlayıcı konturları tarafından belirlenen ikili görüntüleri ele almakla yetinelim. Dijital eğrilerin yayları ve ayrıca dijital çizgilerin bölümleri, düz çizgilerin bölümleri ve eğrilerin yayları tarafından oluşturulan konturları içeren görüntülerin örneklenmesiyle oluşturulur.
Düz çizgi parçalarının ve eğrilerin yaylarının karakteristik özellikleri, dönüşüm sırasında kaybolur. Örneklenmiş bir görüntüyü yeterli büyütmede görüntülerken, bir dizideki tek tek çizgi parçalarını ve eğri yaylarını tanımak genellikle zordur.
dikey ve yatay bölümler. Kontur çizgilerinin - kalınlığı olmayan matematiksel çizgiler - monitör ekranında bağlantılı piksel dizilerinde, yani bir kalınlığa sahip görsel çizgilerde görüntülenmesi nedeniyle işleme sırasında ek zorluklar ortaya çıkar.
Bundan kaynaklanan sorunları ortadan kaldırmak için, ayrıklaştırma sonucunda orijinalden elde edilen görüntüyü iki boyutlu bir hücre kompleksi olarak ele alacağız. Bu durumda
pikseller, bu hücresel kompleksin iki boyutlu öğeleridir. Piksellere ek olarak, çatlaklar ve noktalar var. çatlak
tek boyutlu öğeler olan piksellerin kenarları. Noktalar, çatlakların uç noktaları ve piksellerin köşe noktalarıdır. Noktalar sıfır boyutlu elemanlardır. Yani
Bu nedenle, söz konusu durumda, nesnenin konturu, nesnenin pikselleri ile arka plan arasında sınır oluşturan, bağlı bir kapalı kontur çatlakları dizisidir. Bir kontur, bir tamsayı dizisi olarak tanımlanabilir. nokta koordinatları,
kontur çatlaklarını sınırlandırır. 'de gösterildiği gibi, görüntü düzleminin şu şekilde temsili
hücre kompleksi birçok fayda sağlar. Özellikle bölge sınırı, sıfır alanlı ince bir eğri haline gelir.
Şek. Şekil 1, bir eğri yayı ve bir düz çizgi parçası tarafından oluşturulan bir nesnenin başlangıç konturunun bir örneğini ve bunun bir dizi çatlak olarak dijital eşdeğerini göstermektedir. Farklı yönlerdeki çatlaklara ait noktalar numaralandırılmıştır. Çalışmalarda olduğu gibi, b-elementi ile, bir noktadan başlayıp aynı veya dik yönde bir çatlakla biten, aynı yöndeki bağlantılı bir dizi çatlakları kastediyoruz. Şek. Şekil 1, noktalar arasındaki çatlaklar tarafından oluşturulan b-elemanlarına konturun olası bölümlerinden birini göstermektedir: (0-2), (2-4), (4-6), (6-8), (8 -9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25) ), (25-27), (27-0). Her b elemanı aşağıdaki parametrelerle karakterize edilir: başlangıç noktasına göre yön g (g = 0 - yukarı yön için, 1 - sağa, 2 - aşağı, 3 - sola); l - g yönündeki çatlak sayısı (! = 1,2,...); önceki çatlakların g yönüne göre son çatlağın yönü q (q = -1 - son çatlak g yönüne göre sola yönlendirilir, +1 - sağa, 0 - g yönü ile çakışır) ). Çatlak sayısı l geleneksel olarak b-elemanının "uzunluğu" olarak adlandırılacaktır.b-elemanı için (0-2) g =0, !=3, q =+1. b elemanı (27-0) için g =3, =1, q =0.
Konturdaki dijital çizgilerin parçalarını seçme yöntemi, parçayı oluşturan b-elemanları dizisinin aşağıdaki özelliğini kullanır. Böyle bir dizi, aynı g, q değerlerine sahip b-elemanlarını içerir; uzunlukları !, +1 değerlerini alır. Ve
uzunlukların b-elemanlarının değişimi!, +1, n = Ax = |x1 - x2| tamsayılarının bölünmesiyle elde edilen sürekli kesir tarafından belirlenir. ve m = Ay = |y1 - y2\, burada (x1zy1), (x2,y2) başlangıç koordinatlarıdır
ve segmentin bitiş noktaları: veya
Kesinlik için, n > m olduğunu varsayıyoruz Formül (1)'den aşağıdaki gibi, l - n'yi m'ye bölmenin tamsayı kısmı - dijital düz çizginin segmentinde aynı yöndeki l ardışık çatlak sayısına karşılık gelir. Bitişikteki dikey çatlak ile birlikte, uzunluğun b-elemanını oluştururlar!. k1 uzunluğu l olan ardışık b-elemanları ve uzunluk!+1 olan bir b-elemanı (veya k1 uzunluğu +1 olan ardışık b-elemanları ve bir b-elemanı uzunluğu!) "uzunluk" k1'in bir K1-elemanını oluşturur. "uzunluk" b-elemanı ile benzerlik). Ardışık b-elemanlarından uzunluğu 1 ile farklılık gösteren bir b-elemanı, belirli bir K1-elemanının değiştirilmiş bir b-elemanı olarak adlandırılacaktır. Benzer şekilde, k2 "uzunluk" k1'in ardışık K1-elemanları ve "uzunluk" k1 +1'in bir K1-elemanı (veya "uzunluk" k1 +1'in k2 ardışık K1-elemanları ve "uzunluk" k1'in bir K1-elemanı) oluşur. K2- “uzunluk” elemanı k1. Yani
k + k 2 + kz + ... + kg
devam eden kesrin üyeleri tükenene kadar devam eder. Ardışık K1 öğelerinden (Kg-1 -element) uzunluğu 1 ile farklılık gösteren K1 -elementi (genellikle K-1 -element), bu K2'nin değiştirilmiş K1 -elementini (Kg-1 -element) arayacağız - eleman (Kg -eleman). Böylece, her birine
düz bir çizginin dijital bölümü, elemanları bu bölümün yapısını belirleyen sürekli bir kesire karşılık gelir.
Şekildeki konturda. 1 aşağıdaki dijital düz çizgi segmentleri seçilebilir: 0-3, 3-9, 910, 10-17, 17-0.
3. Konturdaki dijital çizgi segmentlerinin seçimi
Görüntü konturlarını, özellikle ikili görüntüleri, bir kontur oluşturan bir dizi çatlakta işlerken, dizinin çizgi segmentlerini oluşturan kısımlarını seçmek gerekir. Bu problem, kontürün bir dizi L-elemanından sürekli bir kesrin elemanlarını belirleme problemi olarak düşünülebilir. Bu görev doğrunun bir parçasının yapısını, parçanın başlangıç ve bitiş koordinatlarındaki farklılıkların oranı olarak elde edilen, sürekli bir kesrin üyelerinin dizisiyle belirleme probleminin tersidir.
Dijital bir hattın segmentlerini seçme yöntemi, aşağıdaki eylemleri sırayla gerçekleştirmekten oluşur.
1. Çatlaklar dizisindeki b-elemanlarının dizisinin seçimi. Bu eylem, bir tamsayı bölümünün tanımına karşılık gelir! devam atış (1).
2. b-elemanları dizisinde r=1 olan Kg-elemanlarının dizisinin izolasyonu ve her K1-elemanının b-elemanlarından biri diğerlerinden daha fazla veya daha az 1 çatlak içermelidir. Bu eylem, sürekli fraksiyonun (1) k1 -inci öğesinin tanımına karşılık gelir. Yürütüldükten sonra, r'nin değeri 1 artırılmalıdır.
3. Kg-1 elementleri dizisindeki Kg elementleri dizisinin izolasyonu,
ayrıca, her Kg elemanının Kg-1 elemanlarından biri, diğerlerinden daha fazla veya daha az bir K-2 elemanı içermelidir. Bu eylem, devam eden kesrin (1) k(-inci elemanının tanımına karşılık gelir. Yürütüldükten sonra, r'nin değeri 1 artırılmalıdır.
4. Paragraf 3, ardışık Kr öğelerinden hala mümkün olana kadar tekrarlanır.
Km-elementini oluşturur.
5. Sınır noktaları, aynı Kg elemanına dahil olmayan iki bitişik b elemanı arasında belirlenir. Bu noktalar, konturu oluşturan sayısal doğru parçalarının bitiş noktalarıdır.
B-öğeleri dizisindeki çizgi parçalarını seçme algoritmasını düşünün
[b5 (/5,gs,qs)); s = 0.1,...,t - konturu oluşturan L-elemanlarının sırası; x5, y5 - e-th b öğesinin başlangıcının koordinatları; [hu, yy); y = ; r = 0,1,...,!; !< £ - множество
kontur kırılma noktaları Kesme noktaları, yolu oluşturan çizgi parçalarının uç noktalarını tanımlar. Kırılma noktalarını bulmak, konturu oluşturan doğru parçalarını belirlemek demektir.
İncelenen her segment, bir Kg elementinin yanı sıra bir zincir ile karakterize edilir.
atış. Segment tanımanın ilk anında, karşılık gelen sürekli kesrin öğeleri 0'a eşittir. Sırası r ve öğelerin değerleri de dahil olmak üzere Kr-elementinin parametreleri tanınırsa, bir segment tanınmış olarak kabul edilebilir. karşılık gelen sürekli kesir.
1. Başlangıç koşulları.
[b5 (/5, gs, qs)) ve (x5, y5) dizileri verilmiştir.
|x;.,y,) kırılma noktalarının koordinatlarını bulmak gerekir.
k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - devam eden kesir elemanlarının çalışma değerleri.
İlk parçanın başlangıç noktası olarak 5 =0 noktasını alalım; ben = 0; i=0.
2. Sıradaki ilk b-elemanını, ilk düz doğru parçasının başlangıcına kadar alın. Başlangıç noktası x5,y'dir. /=/0 uzunluğu aynı zamanda sürekli kesrin ilk elemanının değeridir.
5:=5+1; k1p:=k1p+1.
3. Bir sonraki b elemanının öncekilerle birlikte bir K0 elemanı oluşturup oluşturmadığını kontrol edin.
3.1. Eğer ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1)) ise Kr-elementinin devamı k0p:= k0p +1; 5:= 5 + 1; ve çizgi segmentinin devamı. 3. öğeye gidin.
3.2. Eğer ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), o zaman doğru parçasının sonu. 5. maddeye gidin.
3.3. Eğer ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), sonra K0 -elementinin tamamlanması; Ї = Ї+1.
4. K'nin (-element.
4.1. (k == 0) ise k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; Km öğesinin başlangıcı.
3. öğeye gidin.
4.2. Eğer ((k IF 0)&&(k == k^)), o zaman k^1p:= k^1p+1; 5:= 5+1; Ki+1 elemanının devamı. 3. öğeye gidin.
4.3. ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^)) ise, o zaman Ї := +1; Km öğesinin sonu.
4. maddeye gidin.
4.4. (^φ0)&&(|k - k1p|>1) ise, segmentin sonu 5. maddeye doğrudan geçiştir.
5. Segmentin sonu.
X] = Xs; y \u003d Uz; k1p:= 0, k2p:= 0,., kіp:= 0; k:= 0, k2:= 0,., k:= 0.
eğer (ler< S), то s:= s +1; переход к п. 2.
Aksi takdirde, L -elemanları dizisinin sonu. Algoritmanın sonu.
Aslında, önerilen algoritma sürekli kesrin öğelerini ve elde edilen her Kt öğesi için bulur ve yeni oluşturulan Kt öğesinin sürekli kesrinin halihazırda oluşturulmuş olana uygun olup olmadığını kontrol eder.
4. Dijital bir hattın bölümlerini seçme programı
Algoritmanın açıklamasından görülebileceği gibi, programlarda hata ayıklama sırasında ortaya çıkan zorluklar nedeniyle kullanımı yapılandırılmış programlama önerileriyle çelişen önemli sayıda koşullu atlama içerir. Ayrıca, önceden parametre sayısı Kt
t değişkeni önceden sınırlandırılmadığından belirlenemez. t değerini sınırla
Bu, görüntünün boyutunu önceden sınırlamak anlamına gelir. Yazılım uygulaması, özellikle önerilen algoritmanın önemsiz yollarla hata ayıklaması, belirtilen nedenlerle önemli ölçüde zordur. Modern nesne yönelimli programlama araçları kullanılırsa, bir yazılım uygulamasını geliştirme ve hata ayıklama zorluklarını azaltmak mümkündür.
Önerilen algoritma, Visual C++ ortamında görüntü işleme için laboratuvar yazılım paketinin bir parçası olan LINESEGM programı biçiminde uygulanmaktadır.
Başlangıç bilgisi olarak, LINESEGM programı, işlenen görüntünün her bir kontur için oluşturulmuş L-eleman dizilerini kullanır.
Programın sonucu, segmentlerin bitiş noktalarının koordinatları ile temsil edilen, her bir kontur için oluşturulmuş dijital düz çizgilerin bağlantılı bir dizisidir.
Algoritmadan da görülebileceği gibi, Kt-l -elemanlarından Kt -elemanları oluşturma işlemleri
t'nin tüm değerleri için aynıdır. Algoritma her çalıştığında başlangıç değeri t = 0'ın 1 arttığına dikkat edin.Özel sınıf CKForLn, algoritmanın işlemlerine karşılık gelen yöntemleri içerir. Algoritmayı uygulayan programın çalışması sırasında, t'deki her 1 artışla, her t değeri için algoritmanın işlemlerini gerçekleştiren işlevleri içeren yeni bir nesne oluşturulur.
Sıfır seviyesinde K0 -elemanlarının K -elemanlarından değil, L - elementlerinden oluştuğunu dikkate alarak
elementler, CKForLn sınıfının özel bir modifikasyonu olan Cmini sınıfı, algoritmayı sıfır seviyesinde uygulamak için yaratılmıştır.
Programın çalışma prensibi, her t değeri için programın, Kt öğesinin parametrelerini belirleyen işlevleri içeren t-inci düzeydeki CKForLn sınıfının bir nesnesini uygulamasıdır. Kt elemanının ilk parametreleri zaten parametrelerdir.
parametreleri CKForLn t-1 sınıfının bir nesnesi tarafından tanımlanan tamamlanmış Kt-l elemanı
Vay seviye.
CKForLn sınıfının nesneleri, koşullar ortaya çıktıkça uygulanır, yani: bir sonraki seviyenin K-elemanını oluşturma ihtiyacı ve özel bir dinamik dizide biriktirilir. Sıfır seviyeli nesne, programın başlangıcında hemen oluşturulur.
Nesnelerin dinamik bir dizide t arttıkça uygulanması, görüntünün boyutuna kısıtlamalar getirmemenizi sağlar. Görüntü boyutu sınırları yalnızca kullanılan bilgisayarın kaynakları tarafından belirlenir.
Programın işleyişini tanımlarken, tamamlanmış bir Kt kavramı kullanılacaktır -
öğe. Tamamlanmış her Kt öğesi, kt Kt-l öğeleri ve kt-l ±1 Kt-2 öğeleri içeren bir değiştirilmiş Kt-l öğesi içerir; bu, tamamlanmamış bir Kt öğesi içermeyen tamamlanmamış bir Kt öğesinin aksine.
CKForLn sınıfı aşağıdaki yöntemleri içerir.
1. Yöntem DK(), (K-elemanını tanımlayın) - bir K-elemanını tanımlayın.
Bir Kt elemanını belirlemek, belirli bir Kt elemanını oluşturan Kt-1 elemanlarının sayısını belirlemek anlamına gelir.
2. Yöntem VK§, (K-elemanını doğrulayın) - daha önce DK() yönteminin işlevi tarafından belirlenen, aynı seviyedeki K-elemanı ile dikkate alınan K-elemanının kimliğini kontrol edin.
3. Yöntem DEO, (K-elemanının sonunu tanımlayın) - K-elemanının sonunu belirlemek için, yani Kt-elemanını tanımlarken, onun değiştirilmiş Kt-1-elemanını bulun. t-1 düzeyinin DE() yöntem işlevi, t düzeyinin DK() yöntem işlevi tarafından çağrılır.
4. VE() Yöntemi,(K öğesinin sonunu doğrulayın) - önceden DE () yönteminin işlevi tarafından tanımlanan değiştirilmiş K öğesiyle dikkate alınan K öğesinin sonunun kimliğini kontrol edin.
Cmini sınıfı, Cmini sınıfının yöntemlerinin L öğeleri üzerinde çalışması ve K0 öğelerini belirlemesi veya kontrol etmesi bakımından CKForLn sınıfının yöntemlerinden farklı olan aynı yöntemleri içerir.
Cmini sınıf yöntemleri
Cmini sınıfının yöntemleri, yöntem fonksiyonunun çağrıldığı anda L-elemanının mevcut sayısından başlayarak, işlenen görüntünün her bir konturları için oluşturulan L-elemanlarının ilk veri dizileri olarak kullanılır.
Cmini sınıfının DK() yönteminin işlevi, sonraki her L öğesinin parametrelerini, eşleşene kadar ilk L öğesinin parametreleriyle karşılaştırır. Parametreler eşleşmezse, DK() işlevi K0 öğesinin tamamlanıp bitmediğini kontrol eder.
iş. Bir K0 elemanı, uzunluğu K0 elemanının diğer L elemanlarından 1 farklı olan değiştirilmiş bir L elemanı ile bitiyorsa tamamlanmış kabul edilir (segmanın başlangıcı için işlem 3.1 - t = 0).
VK() yönteminin işlevi, aşağıdaki k0 L öğelerinin parametrelerinin, daha önce DK() yönteminin işlevi tarafından tanımlanan K0 öğelerinin L öğelerinin parametreleriyle eşleşip eşleşmediğini kontrol eder.
aynı seviye. Mevcut K0 öğesinin parametreleri öncekiyle çakışıyorsa
tanımlandığında, VK() işlevi bir segment devamı işareti oluşturur ve sona erer (segment devamı için işlem 3.1 - t > 0).
Aksi takdirde, VK() işlevi, segmentin sonunun bir işaretini oluşturur ve biter.
DE() yöntemi işlevi, geçerli K0 öğesinin değişip değişmediğini belirlemek için geçerli Kci öğesinin parametrelerini, DK() işlevi tarafından önceden tanımlanan K0 öğesinin parametreleriyle karşılaştırır. Diğer parametreler eşitse, L -elemanlarının sayısı k0
daha önce tanımlanan K0 öğesiyle karşılaştırıldığında değiştirilmiş K0 öğesinin
DK() işlevi 1 ile farklılık göstermelidir (tamamlanmayı belirlemek için işlem 3.2, 3.3
ilk K0 -segmentin elemanı - t = 0). Sonuç - değiştirilmiş K0 öğesinin parametreleri
Cmini sınıfının VE() yönteminde kullanılır.
VE() yöntemi işlevi, geçerli K0 öğesinin parametrelerini, DE() işlevi tarafından önceden tanımlanan değiştirilmiş K0 öğesinin parametreleriyle karşılaştırır.
çakışıyorlar mı (segmentin devamı için işlem 3.2, 3.3 - t > 0). Sonuç - bir eşleşme veya uyuşmazlığın işareti - CKForLn sınıfının VK() yönteminde kullanılır.
CKForLn sınıfının yöntemleri
Yöntemler için oluşturulan K-elemanlarının parametrelerini başlangıç verisi olarak kullanır. alt düzey. Yani Kt elemanının parametrelerini belirlemek için parametreler kullanılır.
zaten inşa edilmiş Kt-l -elemanları.
CKForLn sınıfının t seviyesinin DK() yönteminin işlevi, ^-elementinin parametrelerini belirlerken, önceden tanımlanmış Kt'nin olup olmadığını kontrol eden CKForLn sınıfının t-1 seviyesinin VK() işlevini çağırır. -l öğesinin ardından aynı parametrelere sahip bir Kt-l öğesi gelir. Evet ise, VK() işlev çağrısı tekrarlanır. Bu durumda tekrar sayısı sayılır, yani kt parametresi belirlenir.
Aksi takdirde, t düzeyinin DK() işlevi, değiştirilmiş Kt-l öğesini belirlemek için t-1 düzeyinin DE() işlevini çağırır ve çıkar. Çalışmanın sonunda, CKForLn sınıfının t düzeyinin DK() işlevi parametreleri belirler ve tamamlanmış veya tamamlanmamış bir Kt öğesinin işaretlerini üretir (şu anki ile işlem 4.1, 4.2). maksimum değer t).
CKForLn sınıfının t düzeyinin VK() yönteminin işlevi, aşağıdaki kt Kt öğelerinin parametrelerinin önceden tanımlanmış Kt öğelerinin parametreleriyle aynı olup olmadığını kontrol eder.
aynı düzeydeki DK() yönteminin işlevi. Geçerli Kt elemanının parametreleri ile eşleşirse
DK() işlevi tarafından önceden tanımlanmış Kt -aynı düzeydeki öğe, VK() işlevi
segmentin devamına dair bir işaret oluşturur ve işi tamamlar.
Aksi takdirde, VK() işlevi, segmentin sonunun bir işaretini oluşturur ve çıkar (mevcut t değeri maksimumdan daha az olan işlem 4.1,4.2).
Kt öğesi CKForLn sınıfının DE0 level t yönteminin işlevi, bir Kt öğesinin parametrelerini belirlerken, mevcut Kt öğesinin parametrelerini, DK() işlevi tarafından önceden tanımlanan Kt öğesinin parametreleriyle karşılaştırır ve bunun olup olmadığını belirler. geçerli Kt öğesi değişti. Diğer parametreler eşitse, kt-1 değerleri 1 ile farklılık göstermelidir. Bu koşul karşılanırsa, DE() işlevi, değiştirilen Kt öğesinin bir işaretini üretir ve
sona erer (mevcut maksimum t değerinde işlem 4.3, 4.4).
CKForLn sınıfının t seviyesinin VE() yönteminin işlevi, parametre değerlerinin eşleşip eşleşmediğini belirlemek için geçerli Kt öğesinin parametrelerini DE() işlevi tarafından önceden tahsis edilen değiştirilmiş Kt öğesinin parametreleriyle karşılaştırır.
Mevcut Kt elemanının parametrelerinin değerleri önceki ile çakışırsa
aynı seviyedeki DK() işlevi tarafından tanımlanan VK() işlevi, parametre değerlerinin eşleştiğine ve sonlandırıldığına dair bir işaret üretir (mevcut t değeri maksimumdan daha az olan işlem 4.3,4.4).
Zamanlama diyagramı (Şekil 2) bir düz çizgi parçasının tanınması örneğini kullanarak LINESEGM programının çalışmasını gösterir. Şeklin alt kısmı, aynı ana ve yardımcı yönlere ve farklı uzunluklara sahip L elemanlarından oluşan dijital hattın bir bölümünü göstermektedir.
0 adımında, K0 öğesinin parametrelerini tanımlayan Stіnі sınıfının bir nesnesi oluşturulur.
10. adımda, K0 öğesinin parametrelerinin belirlenmesi tamamlanır ve K1 öğesinin parametrelerini belirlemek için önceden oluşturulmuş nesnenin işlevlerini kullanan CRORGn sınıfından bir nesne 1 oluşturulur. 19. adımda, K1 öğesinin parametrelerinin tanımı tamamlanır ve K2 öğesinin parametrelerini belirlemek için önceden oluşturulmuş nesnelerin işlevlerini kullanan CCROGn sınıfının bir nesnesi 2 oluşturulur. Adım 49'da, K2 öğesinin parametrelerinin belirlenmesi tamamlanır ve K3 öğesinin parametrelerini belirlemek için önceden oluşturulmuş nesnelerin işlevlerini kullanan CRORGn sınıfının bir nesnesi 3 oluşturulur. Adım 79'da,
sonlandırma koşulu. Programın işleyişi ekte detaylı olarak anlatılmıştır.
0-6 bölümünde, iki b-elemanı, bitmemiş bir K0-elemanı oluşturur. Açıktır ki b -
3 uzunluğundaki eleman 3-6 doğru parçasını tamamlar, çünkü 1 uzunluğundaki b-elemanı 6-7 onun devamı olamaz. Böylece, b-elemanı 6-7, dijital hattın segmentinin başlangıcıdır.
Şek. 3, programın nasıl çalıştığına dair bir örnek gösterir. Kıvrımlı okun ikili görüntüsünün konturu, karelerle düz çizgi parçalarına bölünür. Programın sonucu - bir dizi çizgi parçası - dijital eğrilerin yaylarını vurgulamak için kullanıldı. Büyük kareler, dijital eğri yaylarının sınırlarını gösterir.
Programın çalışması, önemli sayıda (2000'den fazla) örnek üzerinde test edilmiştir ve yarı tonlu görüntülerin yapısal analizi çalışmasında kullanılmıştır.
5. Çizgi segmentlerinin tanınması için programın çalışması
iEBESM programının çalışmasını Şekil l'deki örnek üzerinde ele alalım. 4. Şeklin alt kısmı, aynı ana ve yardımcı yönlere ve farklı uzunluklara sahip b-elemanlarından oluşan dijital hattın bir bölümünü göstermektedir. 0-6 bölümünde, iki b-elemanı eksik bir K0- oluşturur.
Pirinç. 3. Konturun yapısal analizi için programın çalışmasına bir örnek - konturun dijital düz çizgilerin bölümleriyle bölümlere ayrılması
öğe. Açıkça, uzunluk 3'ün 3-6 b-elemanı, uzunluk 1'in 6-7 b-elemanı onun devamı olamayacağından, doğru parçasını tamamlar. Böylece, b-elemanı 6-7, dijital hattın segmentinin başlangıcıdır.
Programın düz çizginin bir sonraki parçasını belirleme çalışması, tamamlanan K0 - element 6-10'u belirleyen sıfır seviyesinin OK() fonksiyonu ile başlatılır, b-elemanlarından oluşur.
uzunluklar 1,1,2; k0=2. Bu K0 öğesi, K1 öğesi için başlangıç öğesidir. Program birinci seviyenin bir nesnesini oluşturur ve kontrolü bu nesnenin OK() işlevine aktarır. Düzey 1'in OK() işlevi, düzey 0'ın VKQ işlevini çağırır. VKQ işlevi, K0 öğesi 6-10'un b öğelerinin parametrelerini sonraki b öğeleriyle karşılaştırır ve K0 öğesi 10-14'ün varlığını doğrular,
K0 -element 6-10 ile aynıdır. Devam ederken, VKQ işlevi aşağıdaki b öğelerinin aynı K0 öğesini oluşturmadığını algılar, çıkar ve kontrolü OK() düzey 1 işlevine aktarır Düzey 1 OK() işlevi, düzey 0 OE() işlevini çağırır. b-öğesi 6-7 ile, uzunlukları 1,1,1,2 olan b-elemanlarından oluşan değiştirilmiş bir K0 elemanı 14-19'un varlığını belirler; k0=3, çıkar ve kontrolü seviye 1'deki OK() işlevine aktarır. Bu işlev, iki K0 -
1,1,2, (k1=2) elemanları ve 1,1,1,2 (k0=3) değişti. Program, ikinci seviyenin bir nesnesini oluşturur ve kontrolü bu nesnenin OK() işlevine aktarır. Düzey 2 OK() işlevi, düzey 0 VKQ işlevini çağıran düzey 1 VKQ işlevini çağırır.VKQ işlevi, K0 öğesi 6-10'un b öğelerini aşağıdaki b ile karşılaştırır.
K0 elemanı 6-10 ile aynı olan K0 elemanları 19-23, 23-27'nin varlığını teyit eder, yani K1 elemanı 6-19'da bu K0 elemanları ile aynı sayıda bulunur. Daha sonra, seviye 0'ın VKQ işlevi, seviye 1'in VKQ işlevinin segmentine devam etme işaretiyle kontrolü döndürür. VKQ işlevi, değişen bir K0'ın varlığını belirleyen seviye 0'ın VE0 işlevini çağırır -
27-32 elemanı, K0 elemanı 14-19 ile aynıdır. Böylece, K1-elemanı 19-32 tanımlanır,
K1 öğesi 6-19 ile aynıdır. Ayrıca, seviye 1 VKQ işlevi, K1 öğesi 6-19 ile aynı olan sonraki K1 öğesini belirlemez, çünkü düzey 0 işlevi VE0, b öğesinden başlayarak K1 öğesi 6-19 ile aynı olan değiştirilmiş K1 öğesini belirlemez. 40-41 ve düzey 2'nin OK() işlevinin kontrolünü döndürür. Düzey 2'nin OK() işlevi, düzey 1'in OE() işlevini çağırır; bu, aşağıdakilerden oluşan 32-49 değiştirilmiş bir K1 öğesinin varlığını belirler. K0 elemanları 32-36, 36-40,
40-44, 44-49. Daha sonra K2 elemanı 6-49 belirlenir, seviye 3 nesnesi oluşturulur, değiştirilmiş K2 elemanı 49-79 belirlenir. Bu iki K2 elemanı, K3 elemanı 6-79'u oluşturur. Bu, segmentin yapısını tamamlar, çünkü aşağıdaki b-elemanları 79-81 ve 81-83 bir K0 elemanı oluşturmaz,
K0 öğesi 6-10 ile aynıdır ve seviye 0 VKQ işlevi bir devam bayrağı oluşturmaz
segment. b-elemanları dizisinde, dijital düz çizgi 6-79'un bir segmenti seçilir. Program, b-elemanı 80-82 ile başlayarak bir sonraki segmentin tanımını başlatır.
b. sonuçlar
1. Önerilen yeni algoritma görüntü konturlarında çizgi segmentlerinin seçimi ve algoritmanın önemsiz olmayan bir yazılım uygulaması, bu da görüntü konturlarını çizgi segmentleri dizileri olarak tanıma sorununa kesin bir çözüm elde edilmesini sağlar.
2. Görüntü konturlarında çizgi parçalarını seçmek için algoritmanın yazılım uygulaması kullanılarak yapılır. modern araçlar kullanılan bilgisayarın kaynaklarının kullanımını en üst düzeye çıkarırken, işlenen görüntünün boyutuna açık kısıtlamalar getirmemeyi mümkün kılan nesne yönelimli programlama.
3. Önerilen algoritma ve yazılım uygulaması temelinde, teorik bir çözüm elde edildi ve dijital eğrilerin yaylarının tanınması ve ikili görüntülerin konturunun dijital çizgiler ve dijital eğrilerin yaylarından oluşan bir segment üzerinde bölümlere ayrılması üzerine deneyler yapıldı.
KAYNAKÇA
1. Kovalevsky V.A. Dijital Düz Segmentlerin Ekonomik Görüntü Kodlamasına Uygulamaları, 7. Uluslararası Çalıştay Bildirilerinde, DGCI"97, Montpellier. - Fransa, 1997. - 3-5 Aralık. - S. 51-62.
2. Kalmıkov V.G. İkili görüntülerin konturlarındaki dijital çizgilerin bölümlerini tanımlamak ve tanımak için yapısal yöntem // Parça Zekası. - 2002. - No. 4. - C. 450-457.
3. Kalmykov V.G., Vishnevsky V.V. İkili görüntülerde nesne konturlarının analizi // Matematiksel makineler ve sistemler. - 1997. - No. 2. - S. 68 - 71.
4. Kalmikov V.G. Dijital bir eğrinin yayı - atama ve durgunluk // Sinyal işleme ve görüntü tanıma ve görüntülerin tanınması. Tüm Ukrayna Uluslararası Konferansı Tutanakları. - Kiev. - 2004. - 11 - 15 Zhovten.
Sorunun formülasyonu uygulanmasının amacı ve olanakları ile belirlenir.
Hedef. Dikdörtgen parçaları kaliteli ve kusurlu olarak sınıflandırmak için bir program geliştirin.
Görevin uygulanması için fırsatlar bilgisayarın yeteneklerine göre belirlenir. Bir bilgisayar, sayısal bilgileri algoritmik bir sırayla işleyebilir. Bir bilgisayarın yeteneklerini gerçekleştirmek için çözülmekte olan problemi simüle etmek gerekir.
Bir bilgisayar kullanarak modelleme, gerçek bir nesneden (dünya) verileri ve üzerlerindeki işlemleri kullanarak özelliklerinin kodlanmış bir açıklamasına geçişi ifade eder. Kural olarak böyle bir geçiş birkaç aşamada gerçekleştirilir:
Soyutlama- görev açısından nesnenin en önemli özelliklerinin seçimi.
Görevdeki hedefe uygun olarak gereksiz her şeyi atarak modelleme nesnesinden modelleme konusuna geçmenize izin veren araştırma yapmak gerekir.
Dikdörtgenin diğer dörtgenlerden farkı nedir?
- Karşı tarafların eşitliği.
- Karşı tarafların paralelliği.
- Köşegenlerin eşitliği.
- Tüm açılar doğru.
Sorunu benzersiz bir şekilde çözmek için gereken minimum özellik sayısı nedir?
- 2 karşı kenarın eşitliği + köşegenlerin eşitliği.
- 2 zıt tarafın paralelliği + köşegenlerin eşitliği.
- Üç köşe doğru.
Böylece soyutlama sayesinde sözlü bir bilgi modeli elde ettik. Ancak, yine de bilgisayar tarafından anlaşılmaz. Algoritma olarak sunulan ve yazılımda uygulanan matematiksel modeli anlar.
Görevin uygulanması için metodoloji.
Kaliteli bir parçanın (dikdörtgen) veya kusurlu bir parçanın (dörtgen) çizimi, segmentlerden (LINE komutu) yapılır. grafik sistemi AutoCAD'e aktarılır ve . kntrs.lsp() programı, bir DXF dosyasından çizgi parçası verilerini (köşe koordinatları) okur ve Metin dosyası vrtks.txt'yi sıralı bir sırayla.
vrtks.txt metin dosyası, doğrudan çizimden köşelerin koordinatları alınarak manuel olarak oluşturulabilir.
Geliştirilen rct.lsp programı, vrtks.txt dosyasındaki verileri okumalı, analiz etmeli ve parçanın gereksinimlere uygunluğu (dikdörtgen veya değil) ile ilgili bir kaydı result.txt dosyasına çıkarmalıdır.
Özelliklerin resmileştirilmesi
Parça uzunluklarının eşitliği (kenarlar veya köşegenler): Her parçanın uzunluğu, dikdörtgen bir dikdörtgenin (Pisagor teoremine göre) hipotenüsü olarak, parçaların koordinatlarındaki fark ile belirlenir:
(setq DX12 (mutlak (- X1 X2))) (setq DY12 (mutlak (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Çizgilerin paralelliği: K2=K1, nerede İle düz çizginin eğimidir K=(Y2-Y1)/(X2-X1)
"Doğru Açı" kavramı nasıl resmileştirilir? Görev seti çerçevesinde, bir “Dik Açı”nın varlığı, bölümlerin dikliğinin işareti ile belirlenebilir: K2= -1/K1, nerede İle doğrunun eğimidir. K=(Y-Y0)/(X-X0).
Modelin bilgisayarda görüntülenmesi
Herhangi bir bilgi sonuçta bilgisayarda görüntülenir. ikili sayılar(kodlar) makine içi modele. Daha önce kodlama bir programcı tarafından yapılıyordu. Artık programların çoğu algoritmik dillerde oluşturuluyor.
Uzun zamandır Görüntü Tanıma'nın temellerini içeren genel bir makale, temel yöntemler hakkında bir tür rehber, ne zaman kullanılacağını, hangi görevleri çözdüklerini, akşamları dizinizde neler yapılabileceğini ve neler yapılabileceğini anlatan genel bir makale yazmak istedim. 20 kişilik bir ekip olmadan düşünmemek daha iyidir.
Uzun zamandır Optik Tanıma üzerine bazı makaleler yazıyorum, bu yüzden ayda birkaç kez çeşitli insanlar bu konuyla ilgili sorularıyla bana yazıyor. Bazen onlarla farklı dünyalarda yaşadığınızı hissedersiniz. Bir yandan, bir kişinin büyük olasılıkla ilgili bir konuda profesyonel olduğunu, ancak optik tanıma yöntemleri hakkında çok az şey bildiğini anlıyorsunuz. Ve en can sıkıcı olan şey, yakın bir bilgi alanından mantıklı olan ancak Görüntü Tanıma'da tam olarak çalışmayan bir yöntemi uygulamaya çalışmasıdır, ancak bunu anlamaz ve ona bir şey anlatmaya başlarsa çok rahatsız olur. çok temel. Ve temelden anlatmanın çok zaman aldığını ve çoğu zaman orada olmadığını düşünürsek, daha da üzücü hale geliyor.
Bu makale, görüntü tanıma yöntemleriyle hiç ilgilenmemiş bir kişinin, 10-15 dakika içinde kafasında konuyla ilgili dünyanın belli bir temel resmini oluşturabilmesi ve hangi yöne kazması gerektiğini anlayabilmesi için tasarlanmıştır. Burada açıklanan yöntemlerin çoğu, radar ve ses işlemeye uygulanabilir.
Potansiyel bir müşteriye veya Optik Tanıma yapmaya başlamak isteyen bir kişiye her zaman anlatmaya başladığımız birkaç ilkeyle başlayacağım:
- Bir problemi çözerken, her zaman en basitinden gidin. Bir kişiye turuncu bir etiket asmak, bir kişiyi takip etmekten, onu kademeli olarak vurgulayarak çok daha kolaydır. Daha yüksek çözünürlüklü bir kamera çekmek, süper çözünürlüklü bir algoritma geliştirmekten çok daha kolaydır.
- Optik tanıma yöntemlerinde katı bir problem ifadesi, sistem programlama problemlerinden çok daha önemlidir: TK'deki fazladan bir kelime işin %50'sini ekleyebilir.
- Tanıma problemlerinde evrensel çözümler yoktur. Basitçe "herhangi bir yazıyı tanıyacak" bir algoritma yapamazsınız. Sokaktaki bir işaret ve bir metin sayfası temelde farklı nesnelerdir. Genel bir algoritma yapmak muhtemelen mümkündür (işte Google'dan güzel bir örnek), ancak bu büyük bir ekibin çok çalışmasını gerektirecek ve onlarca farklı alt programdan oluşacaktır.
- OpenCV, birçok yöntemi olan ve neredeyse her sorunun hacminin %50'sini çözebileceğiniz İncil'dir, ancak OpenCV gerçekte yapılabileceklerin sadece küçük bir kısmıdır. Bir çalışmada, sonuçlarda şöyle yazılmıştır: "Sorun OpenCV yöntemleriyle çözülmez, bu nedenle çözülemez." Bundan kaçınmaya çalışın, tembel olmayın ve mevcut görevi her seferinde OpenCV şablonlarını kullanmadan ayık bir şekilde değerlendirin.
Burada sunulan yöntemlerin listesi tam değildir. Yazmadığım kritik yöntemleri yorumlara eklemeyi ve her birine 2-3 eşlik eden kelime atfetmeyi öneriyorum.
Bölüm 1. Filtreleme
Bu grupta, görüntülerdeki ilgi alanlarını analiz etmeden seçmenize izin veren yöntemler yerleştirdim. Bu yöntemlerin çoğu, görüntüdeki tüm noktalara bir tür tek biçimli dönüşüm uygular. Filtreleme düzeyinde, görüntü analiz edilmez, ancak filtrelemeden geçen noktalar ile alanlar olarak kabul edilebilir. özel özellikler.Eşik ikilileştirme, histogram alanı seçimi
En basit dönüşüm, görüntünün eşik ile ikilileştirilmesidir. RGB ve gri tonlamalı görüntüler için eşik, renk değeridir. Böyle bir dönüşümün yeterli olduğu ideal problemler vardır. Beyaz bir kağıt yaprağındaki öğeleri otomatik olarak seçmek istediğinizi varsayalım:
İkilileştirmenin gerçekleştiği eşiğin seçimi, ikilileştirme sürecinin kendisini büyük ölçüde belirler. Bu durumda, görüntü ortalama renkle ikilileştirildi. Tipik olarak, ikilileştirme, uyarlanabilir bir şekilde bir eşik seçen bir algoritma ile yapılır. Böyle bir algoritma, beklenti veya mod seçimi olabilir. Ve histogramın en büyük zirvesini seçebilirsiniz.
İkilileştirme, bir görüntüyü RGB'de değil HSV'de düşünürsek durum da dahil olmak üzere histogramlarla çalışırken çok ilginç sonuçlar verebilir. Örneğin, ilgilendiğiniz renkleri segmentlere ayırın. Bu prensipte hem etiket dedektörü hem de insan derisi dedektörü oluşturmak mümkündür.
Klasik filtreleme: Fourier, LPF, HPF
Radar ve sinyal işlemeden gelen klasik filtreleme yöntemleri, çeşitli Örüntü Tanıma görevlerinde başarıyla uygulanabilir. Saf haliyle görüntülerde neredeyse hiç kullanılmayan radardaki geleneksel yöntem, Fourier dönüşümüdür (daha spesifik olarak, FFT). 1D Fourier dönüşümünün kullanıldığı birkaç istisnadan biri görüntü sıkıştırmadır. Görüntü analizi için genellikle tek boyutlu bir dönüşüm yeterli olmaz, çok daha fazla kaynak yoğun iki boyutlu bir dönüşüm kullanmanız gerekir.
Çok az insan bunu gerçekten hesaplar, genellikle ilgili bölgenin evrişimini zaten olanlarla kullanmak çok daha hızlı ve daha kolaydır. hazır filtre, yüksek (HPF) veya düşük (LPF) frekanslara keskinleştirilmiştir. Böyle bir yöntem elbette spektrum analizine izin vermez, ancak belirli bir video işleme görevinde genellikle ihtiyaç duyulan bir analiz değil, bir sonuçtur.
Çoğu basit örnekler düşük frekansları (Gauss filtresi) ve yüksek frekansları (Gabor filtresi) vurgulayan filtreler.
Her görüntü noktası için bir pencere seçilir ve aynı boyutta bir filtre ile çarpılır. Böyle bir evrişimin sonucu, noktanın yeni değeridir. LPF ve HPF uygulanırken bu türden görüntüler elde edilir:
dalgacıklar
Ama ya sinyalle evrişim için keyfi bir karakteristik fonksiyon kullanırsak? Daha sonra "Dalgacık Dönüşümü" olarak adlandırılacaktır. Dalgacıkların bu tanımı doğru değildir, ancak geleneksel olarak, birçok takımda dalgacık analizi, bu modelin bir modeliyle evrişim kullanarak bir görüntüde rastgele bir model arayışıdır. Dalgacık analizinde kullanılan bir dizi klasik fonksiyon vardır. Bunlar Haar dalgacık, Morlet dalgacık, Meksika şapka dalgacık ve benzerlerini içerir. Hakkında daha önceki makalelerimden birkaçı olan Haar ilkelleri ( , ), iki boyutlu bir uzay için bu tür fonksiyonlara atıfta bulunur.
Yukarıda klasik dalgacıklara 4 örnek verilmiştir. 3B Haar dalgacık, 2B Meyer dalgacık, Mexican Hat dalgacık, Daubechies dalgacık. iyi örnek Dalgacıkların genişletilmiş yorumunun kullanımı, kamaşmanın kendisinin bir dalgacık olduğu gözde kamaşma bulma problemidir:
Klasik dalgacıklar genellikle görüntü sıkıştırma veya sınıflandırmaları için kullanılır (aşağıda açıklanacaktır).
korelasyon
Benim açımdan dalgacıkların böylesine özgür bir yorumundan sonra, onların altında yatan gerçek korelasyondan bahsetmeye değer. Görüntüleri filtrelerken, bu vazgeçilmez bir araçtır. Klasik bir uygulama, ofsetleri veya optik akışları bulmak için video akışı korelasyonudur. En basit kaydırma detektörü aynı zamanda bir anlamda bir fark bağdaştırıcısıdır. Görüntülerin birbiriyle ilişkili olmadığı yerde hareket vardı.
fonksiyon filtreleme
İlginç bir filtre sınıfı, filtreleme işlevleridir. Bunlar, bir görüntüdeki basit bir matematiksel işlevi (çizgi, parabol, daire) algılamanıza izin veren tamamen matematiksel filtrelerdir. Orijinal görüntünün her noktası için, onu oluşturan bir dizi işlevin çizildiği bir birikimli görüntü oluşturulur. En klasik dönüşüm, çizgiler için Hough dönüşümüdür. Bu dönüşümde, her (x;y) noktası için, y=ax+b doğrusu için eşitliğin doğru olduğu bir (a;b) noktaları kümesi çizilir. Güzel fotoğraflar elde edin:
(ilk artı resimde bir yakalama bulan ve böyle bir tanım bulan ve açıklayan için ikinci artı burada gösterileni ilk söyleyen için ikinci artı)
Hough dönüşümü, herhangi bir parametrelenebilir işlevi bulmanızı sağlar. Örneğin çevreler. Herhangi bir şekli aramanıza izin veren değiştirilmiş bir dönüşüm var. Bu dönüşüm matematikçilerin çok hoşuna gidiyor. Ancak görüntüleri işlerken, ne yazık ki her zaman çalışmaz. Çok yavaş hız, ikilileştirme kalitesine çok yüksek hassasiyet. İdeal durumlarda bile başka yöntemlerle geçinmeyi tercih ettim.
Çizgiler için Hough dönüşümünün karşılığı Radon dönüşümüdür. Çok puanın olduğu bir durumda performans kazancı sağlayan FFT üzerinden hesaplanır. Ayrıca, ikilileştirilmemiş bir görüntüye de uygulanabilir.
Kontur filtreleme
Ayrı bir filtre sınıfı, kenarlık ve kontur filtrelemedir. Yollar, bir görüntüyle çalışmaktan o görüntüdeki nesnelerle çalışmaya geçmek istediğimizde çok kullanışlıdır. Bir nesne oldukça karmaşık ancak iyi ayırt edilmiş olduğunda, genellikle onunla çalışmanın tek yolu, konturlarını seçmektir. bir takım algoritmalar var problem çözme kontur filtreleme:En yaygın kullanılanı, iyi çalışan ve uygulaması OpenCV'de olan Kenny'dir (Sobel de oradadır, ancak daha kötü konturlar arar).
Diğer filtreler
Yukarıda, değişiklikleri görevlerin% 80-90'ını çözmeye yardımcı olan filtreler bulunmaktadır. Ancak bunların yanı sıra yerel görevlerde kullanılan daha nadir filtreler de var. Böyle onlarca filtre var, hepsini listelemeyeceğim. Yinelemeli filtreler (örneğin, bir aktif görünüm modeli) ile radon dönüşümü alanındaki klasik dalgacık filtreleme ve analizinin bir alaşımı olan ridgelet ve eğrisel dönüşümler ilgi çekicidir. Işıncık dönüşümü, dalgacık dönüşümü ve mantıksal analizin sınırında güzel bir şekilde çalışır ve konturları vurgulamanıza olanak tanır:
Ancak bu dönüşümler çok özeldir ve nadir görevler için uyarlanmıştır.
Bölüm 2. Filtreleme sonuçlarının mantıksal işlenmesi
Filtreleme, işlemeye uygun bir dizi veri verir. Ancak çoğu zaman bu verileri işlemeden alıp kullanamazsınız. Bu bölüm birkaç klasik yöntemler, görüntüden nesnelerin özelliklerine veya nesnelerin kendilerine geçmenize izin verir.morfoloji
Bana göre filtrelemeden mantığa geçiş matematiksel morfoloji yöntemleridir ( , , ). Aslında bunlar, ikili görüntülerin artırılması ve aşındırılmasının en basit işlemleridir. Bu yöntemler, mevcut öğeleri artırarak veya azaltarak ikili görüntüdeki paraziti gidermenize olanak tanır. Matematiksel morfolojiye dayalı olarak, konturlama algoritmaları vardır, ancak genellikle bir tür hibrit algoritma veya algoritmaları birlikte kullanırlar.
kontur analizi
Filtreleme ile ilgili bölümde, sınırları elde etmek için kullanılan algoritmalardan daha önce bahsedilmiştir. Ortaya çıkan sınırlar oldukça basit bir şekilde konturlara dönüştürülür. Canny algoritması için bu otomatik olarak gerçekleşir, diğer algoritmalar için ek ikilileştirme gereklidir. Örneğin, beetle algoritması ile ikili bir algoritma için bir kontur elde edebilirsiniz.Kontur, bir nesnenin benzersiz bir özelliğidir. Genellikle bu, nesneyi kontur boyunca tanımlamanıza izin verir. Bunu yapmanıza izin veren güçlü bir matematiksel aparat var. Cihaza kontur analizi ( , ) denir.
Dürüst olmak gerekirse, kontur analizini gerçek problemlere uygulamayı hiç başaramadım. Çok ideal koşullar gereklidir. Ya sınır yok ya da çok fazla gürültü var. Ancak, ideal koşullar altında bir şeyi tanımanız gerekiyorsa, kontur analizi harika bir seçenektir. Çok hızlı çalışıyor, güzel matematik ve anlaşılır mantık.
tekil noktalar
Anahtar noktalar, nesnenin kendisiyle veya benzer nesne sınıflarıyla ilişkilendirilmesine izin veren bir nesnenin benzersiz özellikleridir. Bu tür noktaları seçmenin onlarca yolu vardır. Bazı yöntemler, komşu çerçevelerdeki özel noktaları vurgular, bazıları uzun bir süre sonra ve aydınlatma değiştiğinde, bazıları nesne döndüğünde bile aynı kalan özel noktaları bulmanızı sağlar. Çok kararlı olmayan, ancak hızlı bir şekilde hesaplanan özel noktaları bulmamıza izin veren yöntemlerle başlayalım ve sonra artan karmaşıklığa geçeceğiz:Birinci sınıf. Saniyeler boyunca kararlı olan tekil noktalar. Bu tür noktalar, bitişik video kareleri arasında bir nesneyi yönlendirmek veya komşu kameralardan gelen görüntüleri birleştirmek için kullanılır. Bu noktalar, görüntünün yerel maksimumlarını, görüntüdeki köşeleri (detektörlerin en iyisi, belki de Haris dedektörü), dağılım maksimumlarına ulaşıldığı noktaları, belirli gradyanları vb. içerir.
İkinci sınıf. Aydınlatma ve nesnenin küçük hareketlerini değiştirirken sabit olan tekil noktalar. Bu tür noktalar, öncelikle nesne türlerinin eğitimi ve ardından sınıflandırılması için hizmet eder. Örneğin, bir yaya sınıflandırıcı veya bir yüz sınıflandırıcı, tam da bu noktalar üzerine kurulmuş bir sistemin ürünüdür. Daha önce bahsedilen dalgacıklardan bazıları bu noktalar için temel olabilir. Örneğin, Haar ilkelleri, kamaşma araması, diğer belirli özellikleri arayın. Bu noktalar, yönlü gradyanların (HOG) histogramları yöntemiyle bulunan noktaları içerir.
Üçüncü sınıf. kararlı noktalar Tam stabilite sağlayan sadece iki yöntem ve bunların modifikasyonları hakkında bilgim var. Bunlar SURF ve SIFT'dir. Görüntüyü döndürdüğünüzde bile önemli noktaları bulmanızı sağlarlar. Bu tür noktaların hesaplanması diğer yöntemlere göre daha uzun sürer ancak bu yeterlidir. sınırlı zaman. Ne yazık ki, bu yöntemler patentlidir. Rusya'da algoritmaların patentini almak imkansız olsa da, bunu iç pazar için kullanın.
Bölüm 3. Eğitim
Hikayenin üçüncü bölümü, doğrudan görüntü ile çalışmayan, ancak karar vermenize izin veren yöntemlere ayrılacaktır. Temel olarak, bunlar çeşitli makine öğrenimi ve karar verme yöntemleridir. Son zamanlarda, Yanyks bu konuda Habr'da bir kurs yayınladı, çok iyi seçim. İşte metin versiyonunda. Konuyla ilgili ciddi bir çalışma için bunlara bakmanızı şiddetle tavsiye ederim. Burada özellikle örüntü tanımada kullanılan birkaç temel yöntemi tanımlamaya çalışacağım.Durumların %80'inde tanıma probleminde öğrenmenin özü şu şekildedir:
Birkaç nesne sınıfının bulunduğu bir test örneği var. Fotoğrafta bir kişinin varlığı/yokluğu olsun. Her görüntü için, Haar, HOG, SURF veya bazı dalgacık gibi bazı özellikler tarafından vurgulanan bir dizi özellik vardır. Öğrenme algoritması, yeni görüntüyü analiz edebileceği ve görüntüde hangi nesnelerin olduğuna karar verebileceği böyle bir model oluşturmalıdır.
Nasıl yapılır? Test görüntülerinin her biri, özellik uzayında bir noktadır. Koordinatları, görüntüdeki her özelliğin ağırlığıdır. İşaretlerimiz şöyle olsun: “Gözlerin varlığı”, “Burun varlığı”, “İki elin varlığı”, “Kulakların varlığı” vb. Tüm bu işaretleri elimizdeki dedektörlerle tahsis edeceğiz, insana benzer vücut parçaları üzerinde eğitilmiştir. Böyle bir boşluktaki bir kişi için doğru nokta olacaktır. Maymun için, at için nokta. Sınıflandırıcı bir örnek örnek üzerinde eğitilir. Ancak fotoğrafların tamamında eller görünmüyordu, diğerlerinin gözleri yoktu ve üçüncüsü maymunda bir sınıflandırıcı hatasından dolayı insan burnu vardı. Eğitilebilir insan sınıflandırıcı, öznitelik alanını şu şekilde otomatik olarak böler: eğer ilk öznitelik 0,5 aralığındaysa
Birçok sınıflandırıcı var. Her biri bazı görevlerinde daha iyi çalışır. Belirli bir görev için bir sınıflandırıcı seçme görevi büyük ölçüde bir sanattır. Konuyla ilgili güzel resimler var.
Basit durum, tek boyutlu ayırma
Özellik uzayı tek boyutlu olduğunda ve 2 sınıfı ayırmamız gerektiğinde en basit sınıflandırma örneğini ele alalım. Durum göründüğünden daha sık meydana gelir: örneğin, iki sinyali ayırt etmeniz veya bir deseni bir örnekle karşılaştırmanız gerektiğinde. Diyelim ki elimizde bir eğitim örneği var. Bu durumda, X ekseninin bir benzerlik ölçüsü olacağı ve Y ekseninin böyle bir ölçü ile olay sayısı olacağı bir görüntü elde edilir. İstenen nesne kendisine benzer olduğunda sol Gauss elde edilir. Benzer olmadığında - doğru. X=0.4 değeri, örnekleri ayırır, böylece hatalı bir karar, herhangi bir yanlış karar verme olasılığını en aza indirir. Sınıflandırmanın görevi böyle bir ayırıcı arayışıdır.
Küçük not. Hatayı en aza indiren kriter her zaman optimal olmayacaktır. Aşağıdaki grafik, gerçek bir iris tanıma sisteminin grafiğidir. Böyle bir sistem için kriter, bir yabancının nesneye yanlış kabulü olasılığını en aza indirecek şekilde seçilir. Böyle bir olasılığa "birinci tür hata", "yanlış alarm olasılığı", "yanlış pozitif" denir. İngiliz literatüründe "Yanlış Erişim Oranı".
) AdaBusta en yaygın sınıflandırıcılardan biridir. Örneğin, Haar şelalesi bunun üzerine inşa edilmiştir. Genellikle ikili sınıflandırma gerektiğinde kullanılır, ancak hiçbir şey daha fazla sınıf için öğretimi engellemez.
SVM ( , , , ) Birçok uygulamaya sahip en güçlü sınıflandırıcılardan biridir. Prensip olarak, karşılaştığım öğrenme görevlerinde adabusta'ya benzer şekilde çalıştı. Oldukça hızlı kabul edilir, ancak eğitimi Adabusta'nınkinden daha zordur ve doğru çekirdeğin seçimini gerektirir.
Ayrıca sinir ağları ve regresyon vardır. Ancak bunları kısaca sınıflandırmak ve nasıl farklı olduklarını göstermek için bundan çok daha büyük bir makaleye ihtiyaç vardır.
________________________________________________
Umarım matematiğe ve açıklamaya dalmadan kullanılan yöntemlere hızlı bir genel bakış sunabilmişimdir. Belki bu birine yardımcı olur. Tabii ki, makale eksik olmasına ve stereo görüntülerle çalışma veya Kalman filtresiyle LSM hakkında veya uyarlanabilir Bayes yaklaşımı hakkında bir kelime yok.
Makaleyi beğendiyseniz, mevcut ImageRecognition sorunlarının nasıl çözüldüğüne dair örneklerle ikinci bölümü yapmaya çalışacağım.
Ve sonunda
Ne okumalı?1) Bir zamanlar B. Yana'nın basit ve net bir şekilde yazılmış, ancak aynı zamanda neredeyse tüm matematiğin verildiği "Dijital Görüntü İşleme" kitabını gerçekten beğendim. Mevcut yöntemlere aşina olmak için iyi.
2) Türün klasiği R Gonzalez, R. Woods "Digital Image Processing". Nedense benim için ilkinden daha zordu. Çok daha az matematik, ancak daha fazla yöntem ve resim.
3) “Makine görme problemlerinde görüntü işleme ve analiz” - PhysTech bölümlerinden birinde verilen bir ders temelinde yazılmıştır. Birçok yöntem ve ayrıntılı açıklamaları. Ama bence, kitabın iki büyük dezavantajı var: kitap, onunla birlikte gelen yazılım paketine güçlü bir şekilde odaklanıyor, kitapta çok sık basit bir yöntemin açıklaması, çıkarılması zor olan matematiksel bir ormana dönüşüyor. yöntemin yapısal diyagramı. Ancak yazarlar, neredeyse tüm içeriğin sunulduğu uygun bir site yaptılar - wiki.technicalvision.ru
4) Bana öyle geliyor ki, Görüntü Tanıma ve Makine Öğrenimi yaparken ortaya çıkan dünyanın resmini yapılandıran ve birbirine bağlayan iyi bir kitap, Jeff Hawkins'in “On Intelligence” adlı kitabıdır. Doğrudan yöntemler yoktur, ancak doğrudan görüntü işleme yöntemlerinin nereden geldiği hakkında düşünülmesi gereken birçok düşünce vardır. Onu kavradığınızda, zaten insan beyninin yöntemlerini, ancak video işleme görevlerinde gördüğünüzü anlıyorsunuz.
