Object-Counter

simple python program that counts the objects in an image file

Original Image

Algorithms

Levialdi’s Shrinking Algorithm

Article: S. Levialdi. 1972. On shrinking binary picture patterns. Commun. ACM 15, 1 (January 1972), 7-10.

Levialdi’s shrinking algorithm shrinks every connected component in a binary image to a single isolated point to the upper right corner of its bounding rectangle and erases it.

Deletion Condition	Augmentation Condition
Delete 1-valued-pixel if it has the following neighborhood	Change a 0-valued-pixel p to a 1-valued pixel if it has a following neighborhood

Two Sub-fields Algorithm

Article: Gökmen, Muhittin & W Hall, Richard. (1990). Parallel shrinking algorithms using 2-subfield approaches. Computer Vision, Graphics, and Image Processing. 52. 191-209.

In this approach, the image space is partitioned like a checkerboard into two disjoint sets

where 1 and 2 denote the two distinct subfields

Before going into the conditions, we have to define some variables.

• 8-neighbors of the pixel p = Surrounding pixels of p.

p1, p2, p3, ...., pn are 8 neighbors of p.

• B(p) = Number of 1's in pixel p's 8-neighborhood.
• C(p) = Number of distinct sets of 1's in pixel p's 8-neighborhood. (Can be calculated from T(p))
• T(p) = Number of 0-to-1 transition in the 8-neighbors.

For instance;

Deletion Condition

A pixel p = 1 is deleted

1. B(p) = 0 (i.e., isolated point), or
2. All of the following conditions are satisfied:
   • C(p) = 1
   • If B(p) = 1 then p1 = p7 = 0
   • p’s 8-neighborhood contains a 3-length or longer run of 4-connected zeros

Examples that satisfy deletion condition can be found at docs/tsf_del_examples.png

Augmentation Condition

A pixel p = 0 is augmented (changed to 1) if both of the following conditions are satisfied

1. C(p) = 1
2. p8 = p2 = 1 or p8 = p6 = 1

Examples that satisfy augmentation condition can be found at docs/tsf_aug_examples.png

Important Note: In both of the algorithms variable that holds number of objects needs to be incremented every time the programs encounters with an isolated pixel(i.e, all of the 8-neighbors are 0 or B(p) = 0)

Output

Output of the program is a .csv file including file name, which algorithm is used, number of objects and the number of iterations.

File: NCC16_ITER84.png	Algorithm: Levialdi	NCC: 16	Iterations: 84
File: NCC16_ITER84.png	Algorithm: TSF	NCC: 16	Iterations: 34
File: random-out.jpg	Algorithm: Levialdi	NCC: 32	Iterations: 12
File: random-out.jpg	Algorithm: TSF	NCC: 32	Iterations: 6
File: NCC5_ITER48.png	Algorithm: Levialdi	NCC: 5	Iterations: 47
File: NCC5_ITER48.png	Algorithm: TSF	NCC: 5	Iterations: 14
File: random-out.jpg	Algorithm: TSF	NCC: 42	Iterations: 8
File: random-out.jpg	Algorithm: TSF	NCC: 42	Iterations: 8

TODO

• delete previous image before opening a new picture
• image saved notification pop-up
• improve the draw feature
• date stamp to the output file
• separate front-end and back-end

---

All of the images, quoted sentences and materials (excluding .gif's and output.csv) used in README.md are from the slides of Prof. Dr. Muhittin Gokmen