Відстеження контуру

У комп'ютерному зорі об'єкти інтересу часто представляють як області з $1$ у бінарному зображенні (бітовій матриці). Важливим завданням при ідентифікації об'єктів є трасування контуру (також званого межею) об'єкта.

Ми припускаємо, що на межах бітмапи немає жодних $1$. Щоб обвести контур одного об'єкта, можна скористатися процедурою, що називається алгоритм Мура для відстеження межі, наступним чином:

1. Скануємо від верхнього ряду до нижнього, зліва направо у кожному ряду, доки не знайдемо піксель об'єкта. Назвемо цей піксель b_0, а його західного сусіда з фону — c_0.

2. Перевіряємо $8$ сусідів b_0, починаючи з c_0 і рухаючись за годинниковою стрілкою. Нехай b_1 — це перший зустрінутий сусідній піксель об'єкта, а c_1 — сусід з фону, що безпосередньо передує b_1. Зберігаємо позиції b_0 і b_1, додаємо b_0 та b_1 до контуру.

3. Присвоюємо b = b_1, c = c_1.

4. Позначимо $8$ сусідів $b$, починаючи з $c$ та рухаючись за годинниковою стрілкою, як n_1, n_2, $\dots$, n_8. Знаходимо першого сусіда-об'єкта n_k у цій послідовності.

5. Присвоюємо b = n_k, c = n_{k-1}. Додаємо $b$ до контуру.

6. Повторюємо кроки $4$ і $5$, доки b = b_0 і наступна знайдена точка контуру — b_1. Останні дві точки b_0 та b_1 повторюються і не повинні заноситись у контур знову.

Перші кроки алгоритму ілюстровано на рисунку нижче (у цій бітмапі тільки пікселі на межі мають значення $1$):

У цій задачі вам задано бітмапу з не більше ніж $200$ рядками та $200$ стовпцями. Бітмапа містить кілька об'єктів. Ви маєте визначити довжину контуру кожного об'єкта в бітмапі, скориставшись викладеною вище процедурою. У бітмапі яскравість пікселя $0$ означає фон, а $1$ — піксель об'єкта. Два пікселі з інтенсивністю $1$ належать одному об'єкту, якщо існує шлях з одного пікселя до іншого, що складається лише з $1$, і шлях дозволяє рухатися у будь-якому з $8$ напрямків компаса. На межах бітмапи (перший рядок, останній рядок, перший стовпець, останній стовпець) містяться лише фонові пікселі. Будь-який об'єкт, що складається з менше ніж $5$ пікселів, слід ігнорувати, оскільки це, ймовірно, шум. Жоден з об'єктів у бітмапі не містить отворів. Еквівалентно, для будь-якої пари фонових пікселів у бітмапі існує шлях із фонових пікселів, що використовує лише $4$ основні напрямки компаса ($N$, $S$, $E$, $W$).