Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 211. (April 2009)

I. 211. Wire frames can be used to give simpler description of objects of an image. The main idea is to find a one-pixel-wide ``middle line'' of the object: this way less information is needed, and objects can be compared more easily. Frames are useful, for example, in character recognition.

Given a black and white image, your program should find and display the frame of the black components. Each frame should be one pixel wide, should preserve the connectedness of the original object and should keep the endpoints.

The algorithm for creating frames is described in the following. Black pixels are encoded by 1 and white pixels by 0. When creating the frame by narrowing, only contour points of the object can be changed. (A point is said to be contour point if it has value 1, and there is at least one 0 value among its 8 neighbours.) Neighbouring pixels are denoted as can be seen in the first table.

First step. Pixel s0 is deleted, if each of the following four conditions are satisfied:

Here #Neighbours (s0) is the number of neighbours of pixel s0 with value 1, while Changes (s0) is the number of changes of 0s into 1s (or vice versa) in the sequence s1,s2,...,s7,s8,s1.

In the example, Átmenet (\tt s_{0}\text{)} = 3 means Changes (\tt
s_{0}\text{)} = 3.

Second step. Conditions i. and ii. are unchanged, and instead of iii. and iv., consider

and delete pixels according to these rules.

In the first step, all contour points of the object are scanned, then pixels satisfying the 4 conditions are marked as ``to be deleted''. You should delete pixels only after the scanning process has been finished. Then, in the second step, you repeat the same process, but with the second set of conditions.

Step 1 and 2 should be repeated until there is no change in the resulting figure. The frame is now complete.

The command line argument of your program is the name of a black and white BMP image. The output should be the original image together with its frame displayed on the screen. If you prefer, you can use a different image format (e.g. RAW) as well, but then the command line argument of your program should consist of the vertical and horizontal dimensions of the image and the name of the image file.

The source code of your program (i211.pas, i211.cpp, ...) and a short documentation (i211.txt, i211.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling, further, the possible parameters of your program.

(10 pont)

Deadline expired on May 15, 2009.


Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról

A feladat stílusa eltér a megszokottól. Egyrészt grafikai programozás feladat ritkábban fordul elő, másrészt egy megadott algoritmust kellett kódolni. Az algoritmus viszonylag összetett és több lépésből áll. Megértése komoly próbatétel volt a versenyzők számára. Különböző programozási környezetekben eltérő nehézséget jelentett a képállomány beolvasása, majd megjelenítése. Többen kerestek a grafika kezeléséhez programkönyvtárakat. Ezekben eltérő eszközök, eljárások és függvények álltak rendelkezésre a grafikai probléma megoldásához. A vizuális környezetek, illetve ezek programozási eszközei, készen tartalmazzák a kép beolvasást és módosítást. Így, amíg például freepascalban a BMP-állományok szerkezetét is meg kellett ismerni a beolvasás kódolásához, addig delphiben erre kész komponens, illetve metódus van. Persze nem felesleges a képállományok szerkezetének megismerése se, de ez most plusz feladatot jelentett.

Minta megoldásként Turbo Delphi környezetben készült megoldást mutatunk be. A tömörített állomány több fekete-fehér képet tartalmaz, amelyekkel a működés jól tesztelhető.

megoldas.zip


Statistics:

8 students sent a solution.
10 points:Horváth 135 Loránd, Kővágó Zoltán, Szabó 928 Attila, Uray Marcell János.
7 points:2 students.
2 points:2 students.

Problems in Information Technology of KöMaL, April 2009