PROJE EKİBİ
CANBERK KOÇ - ÇAĞRI ULAŞ
PROJENİN AMACI
PROJENİN AMACI
Projenin amacı günlük yaşamda çoktan seçmeli sınav kağıtlarının okunmasını daha kolay hale getirebilmektir. Bunun için OpenCv kütüphanesi ve C++ diliyle geliştirilmiş bir algoritma kullanılmıştır.
Algoritmanın Adımları:
Algoritma 7 ana adımdan oluşmuştur bunlar şu şekilde ifade edilebilir:
- Alınan resmi siyah beyaz hale getirme.
- Hough dönüşümü kullanılarak sayfadaki kenarları bulma.
- Kesit oluşturmak için kenarların kesişme noktalarını bulma.
- Kesit'e perspektif dönüşüm uygulama (Kuş bakışı hale getirme).
- Resimdeki daireleri bulmak için Hough dönüşümü kullanma.
- Daireleri satır ve sütunlar halinde sıralama.
- %30'dan fazlası dolu olan daireleri dolu kabul etme
1.Alınan resmi siyah beyaz hale getirme:
Resmi siyah beyaz hale getirme ileride kullanılacak Hough dönüşümü için önemlidir. Bunu yapmak için Gaussian blur tekniğiyle istenmeyen gürültü noktalardan kurtulunur ve adaptif eşik değeri işleme ile resim temiz bir hale getirilir.
2.Hough dönüşümüyle sayfadaki kenarları bulma:
Resimde kenarları tespit etmek için probablistik(olasılıksal) Hough dönüşümü kullanılarak ana çerçeve belirlenir. Bu algoritma resimdeki her noktaya giderek açısal olarak bu noktaların kenar oluşturup oluşturmadığına bakar. Her nokta ve açıyı taradığı için algoritmadaki en maliyetli işlem budur.
3.Kesit oluşturmak için kenarların kesişme noktalarını bulma:
Kesişim noktalarını bulmak için bir dizi sıralama yapılmalıdır. Ve bu işlem için noktaların toplamının en yoğun olduğu yerler bulunur.
4.Kesit'e perspektif dönüşüm uygulama (Kuş bakışı hale getirme):
OpenCv kütüphanesinin fonksiyonlarından dönüşüm matrisi oluşturulur ve buna perspektif dönüşüm fonksiyonu uygulanır.
5.Resimdeki daireleri bulmak için Hough dönüşümü kullanma:
OpenCv kütüphanesinin HoughCircles fonksiyonu kullanılarak resim üzerindeki bütün seçim daireleri bulunur.
6.Daireleri satır ve sütunlar halinde sıralama:
Çizilen daireler kordinatlarına göre gruplanarak satır ve sütunlara bölünür.
7.%30'dan fazlası dolu olan daireleri dolu kabul etme:
Dairelerin içindeki piksel yoğunlukları ölçülerek yüzde 30'dan fazlası dolu olan daireler işaretlenmiş olarak kabul edilir.
Algoritmanın Karmaşıklığı:
Geliştirilen algoritma içinde kullanılan OpenCv fonksiyonlarının karmaşıklıkları bizi analiz esnasında etkilemektedir. Eğer bu fonksiyonlar kullanılmasaydı algoritmanın en karmaşık yeri dairelerin dolu olan alanlarının bulunması için yapılan 3 for döngüsü olacak ve karmaşıklık 0(N^3) olacaktı. Kullanılan fonksiyonların karmaşıkları şu şekildedir:
GaussianBlur fonksiyonu için karmaşıklık O(ÇekirdekYüksekliği X ÇekirdekGenişliği X ResimYüksekliği X ResimGenişliğidir)'dir. Bizim algoritmamızda bu O(N^2) olarcaktır.
C++ Standart Kütüphanesi sıralama algoritmasının karmaşıklığı O(nlogn)'dir.
Hough Dönüşümü yukarıda da belirtildiği gibi en maliyetli olan kısımdır bu kısmın karmaşıklığı O(ResimBoyutu^(ParametreSayısı-2)) bizim algoritmamız için bu oran ResimBoyutu = N ve ParametreSayısı=5 olacağı için O(N^3) olacaktır. Parametre olarak kastedilen ise gürültüleri temizlemek için kullanılacak yakınlık eğrileridir.
Bu durumda en karmaşık kısım O(N^3) olacağı için ve bu karmaşıklık diğerlerini kapsayacağı için karmaşıklık O(N^3)'tür.
Hiç yorum yok:
Yorum Gönder