Kontur İzləmə

Kompüter görməsində maraq obyektləri tez-tez binar təsvirin (bitmapın) daxilində $1$-lər kimi təmsil olunur. Obyektlərin identifikasiyası üçün vacib tapşırıqlardan biri, obyektin konturunu (həmçinin sərhəd və ya kənar adlandırılır) izləməkdir.

Qəbul edilir ki, bitmapın sərhədlərində heç bir $1$ yoxdur. Tək bir obyektin konturunu izləmək üçün Moore sərhəd izləmə alqoritmindən aşağıdakı kimi istifadə edə bilərik:

1. Yuxarı sətrdən aşağıya, hər sətrdə isə soldan sağa doğru skan et, bir obyekt pikseli tapana kimi davam et. Bu pikselə b_0 deyək, onun qərb istiqamətində fon qonşusuna isə c_0 deyək.

2. b_0 pikselinin $8$ qonşusunu, c_0-dan başlayaraq saat əqrəbi istiqamətində, yoxla. İlk tapılan obyekt pikselini b_1, b_1-dən əvvəlki fon qonşusunu isə c_1 adlandır. b_0 və b_1-in koordinatlarını yadda saxla və həm b_0, həm də b_1-i kontura əlavə et.

3. b = b_1, c = c_1 kimi təyin et.

4. $b$-nin $8$ qonşusunu, $c$-dən başlayaraq saat əqrəbi istiqamətində, n_1, n_2, $\dots$, n_8 kimi adlandır. Bu ardıcıllıqda ilk obyekt qonşusu n_k-nı tap.

5. b = n_k, c = n_{k-1} kimi təyin et. $b$ pikselini kontura əlavə et.

6. b = b_0 və növbəti tapılan kontur nöqtəsi b_1 olana qədər $4$ və $5$-ci addımları təkrarla. Son iki nöqtə b_0 və b_1 təkrarlanır və onları kontura yenidən əlavə etmək lazım deyil.

Alqoritmin ilk addımları aşağıdakı şəkildə göstərilmişdir (bu bitmapda yalnız sərhəddəki piksellər $1$ kimi işarələnib):

Bu məsələdə sizə ən çoxu $200$ sətir və $200$ sütunlu bitmap veriləcək. Bitmapda bir neçə obyekt ola bilər. Yuxarıdakı prosedura əsaslanaraq, bitmapdakı hər bir obyektin konturunun uzunluğunu müəyyən etməlisiniz. Bitmapda $0$ intensivlikli piksel fonu, $1$ intensivlikli piksel isə obyekt pikselini təmsil edir. İki $1$ intensivlikli piksel yalnız $1$-lərdən ibarət olan, $8$ əsas kompas istiqamətindən istənilən birində keçilə bilən bir yol varsa, eyni obyektə aiddir. Bitmapın sərhədləri (birinci sətr, sonuncu sətr, birinci sütun, sonuncu sütun) yalnız fon piksellərindən ibarətdir. $5$ piksel sayıdan az olan obyektlərə məhəl qoyulmur, çünki onların səs-küy olduğu güman edilir. Bitmapdakı heç bir obyektin boşluğu (daxili boşluq) yoxdur. Başqa sözlə, bitmapdakı istənilən iki fon pikselləri arasında yalnız $4$ əsas kompas istiqamətindən ($N$, $S$, $E$, $W$) istifadə olunmaqla fon piksellərindən ibarət yol mövcuddur.