Ланцюговий код

У чорно-білому (двохрівневому) зображенні групи з'єднаних чорних пікселів можуть вважатися переднім планом або об'єктами, тоді як білі пікселі утворюють фон. Кожну множину з'єднаних чорних пікселів можна повністю описати, перелічивши координати пікселів на її межі проти годинникової стрілки, починаючи з будь-якої точки межі. Цей список пікселів, у свою чергу, можна подати як послідовність напрямків до наступного пікселя у списку. Така послідовність напрямків називається ланцюговим кодом (chain code) об'єкта і точно описує форму незалежно від її розташування.

Існує $8$ можливих напрямків від одного пікселя до сусіднього, й хоча нумерація цих напрямків є довільною, рис. 1 показує стандартну конвенцію. Напрямок $0$ означає "праворуч", $2$ — "безпосередньо вгору", $1$ знаходиться під кутом $45$ градусів між $0$ та $2$, і так далі.

Два чорні пікселі вважаються сусідніми, якщо квадрат відстані між ними не перевищує $2$. Це ґрунтується на стандартній графічній системі координат з пікселем у кожній цілочисельній точці. Два пікселі вважаються сполученими, якщо між ними можна провести неперервний шлях із сусідніх пікселів. З'єднана область — це множина чорних пікселів, де всі елементи поєднані один з одним. Межовим пікселем з'єднаної області (далі — області) називають піксель у межах області, що має хоча б одного сусіда (у чотирьох основних напрямках компаса), який не є чорним. Вважайте, що в області немає дірок, тобто існує лише одна межа.

Ланцюговий код області може починатися з будь-якого пікселя на межі. Він формується шляхом пошуку наступного сусіднього межового пікселя у напрямку проти годинникової стрілки, запису напрямку ($0$-$7$) у вихідний буфер і продовження процесу з нового пікселя. Коли процес повертається до стартового пікселя, ланцюговий код завершено. Вихідний буфер містить послідовність напрямків, що утворюють ланцюговий код, за якими початкову множину пікселів можна відновити, починаючи з будь-якої позиції зображення.

Як приклад, ланцюговий код області на рис. 2 становить $446567001232$. Ланцюговий код однозначно визначає форму області, хоча її положення невідоме. За самим лише ланцюговим кодом можна визначити ознаки форми, такі як периметр та площу (кількість пікселів області). Необхідно написати програму, що обчислює площу з'єднаної області, маючи лише її ланцюговий код.