Kontur İzləmə
Kompüter görmə sahəsində maraq obyektləri tez-tez ikili təsvirlərdə (bitmap) 1 ilə təmsil olunan bölgələr kimi göstərilir. Obyektlərin tanınmasında mühüm vəzifələrdən biri obyektin konturunu (sərhədini) izləməkdir.
Bitmap sərhədlərində heç bir 1 olmadığını qəbul edirik. Tək bir obyektin konturunu izləmək üçün aşağıdakı Moore sərhəd izləmə alqoritmindən istifadə edə bilərik:
Üst sıradan alt sıraya, hər sırada soldan sağa doğru tarayın, obyekt pikseli tapılana qədər. Bu obyekt pikselinə b0 və onun qərb fon qonşusuna c0 deyin.
b0 pikselinin 8 qonşusunu, c0 pikselindən başlayaraq saat əqrəbi istiqamətində yoxlayın. b1 ilə ilk obyekt qonşu pikselini və b1 pikselindən dərhal əvvəlki fon qonşusunu c1 olaraq təyin edin. b0 və b1 yerlərini yadda saxlayın və b0 və b1 kontura əlavə edin.
b = b1 və c = c1 təyin edin.
b pikselinin 8 qonşusunu, c pikselindən başlayaraq saat əqrəbi istiqamətində, n1, n2, ..., n8 olaraq təyin edin. Bu ardıcıllıqda ilk obyekt qonşusu nk tapın.
b = nk, c = n(k-1) təyin edin. b kontura əlavə edin.
b = b0 və növbəti kontur nöqtəsi b1 tapılana qədər 4 və 5 addımlarını təkrarlayın. Son iki nöqtə b0 və b1 təkrarlanır və kontura yenidən əlavə edilməməlidir.
Alqoritmin ilk addımları aşağıdakı şəkildə göstərilmişdir (bu bitmapda yalnız sərhəddəki piksellər 1 ilə işarələnmişdir):
Bu məsələdə, sizə ən çox 200 sıra və 200 sütun olan bir bitmap veriləcək. Bitmap bir neçə obyekt ehtiva edir. Yuxarıdakı prosedurdan istifadə edərək bitmapdakı hər bir obyektin kontur uzunluğunu müəyyən etməlisiniz. Bitmapda 0 piksel intensivliyi fonu, 1 piksel intensivliyi isə obyekt pikselini təmsil edir. İki 1 intensivlikli piksel, yalnız 1 olan bir yoldan bir pikseldən digərinə keçid varsa, eyni obyektə aiddir və yol 8 kompas istiqamətinin hər hansı birində izlənilə bilər. Bitmapın sərhədləri (ilk sıra, son sıra, ilk sütun, son sütun) yalnız fon piksellərini ehtiva edir. 5 piksel az olan hər hansı bir obyekt nəzərə alınmamalıdır, çünki bu, çox güman ki, səs-küydür. Bitmapdakı obyektlərin heç birində deşik yoxdur. Eyni şəkildə, bitmapdakı hər bir fon piksel cütü üçün yalnız 4 əsas kompas istiqamətini (N, S, E, W) izləyən fon piksellərindən ibarət bir yol mövcuddur.
Giriş verilənləri
Giriş bir neçə haldan ibarətdir. Hər bir hal bir sətirdə bitmapdakı sıra (R) və sütun (C) sayını göstərən iki müsbət tam ədədlə başlayır. Bitmap, R sətirində hər biri C uzunluğunda 0 və 1 simlərindən ibarət olan bir sətirdə verilir. Giriş R = C = 0 ilə başlayan bir hal ilə tamamlanır. Son hal işlənməməlidir.
Çıxış verilənləri
Hər bir hal üçün, hal nömrəsini öz sətirində çap edin. Növbəti sətirdə, bitmapda tapılan bütün obyektlərin kontur uzunluqlarını artan sırayla çap edin. Kontur uzunluqlarını həmin sətirdə bir boşluqla ayırın. Əgər bitmapda ən az 5 piksel olan obyekt yoxdursa, əvəzinə 'obyekt tapılmadı' sətirini çap edin.