DIP+CV · Programming Exercise

EP06_02 — 🟢 Marker Filtering by Circularity

6.14.2 EP06_02 🟢 Marker Filtering by Circularity

After image segmentation, it is common for several connected components to be identified. In applications such as document rectification, only a few of these components correspond to the reference markers used for image alignment. A criterion often employed to select these markers is circularity, which measures how close a component’s shape is to a circle.

In this exercise, each component is described by its area \(A\) and its perimeter \(P\). The goal is to compute its circularity and decide, based on a provided threshold, whether the component should be accepted or rejected as a marker candidate.

6.14.2.1 📋 Implementation Guidelines

  1. Quantity: Read the integer \(N\) (number of candidates) and the circularity threshold \(C_{\text{limiar}}\) (real number).
  2. Candidate data: For each of the \(N\) candidates, read the area \(A\) (integer) and the perimeter \(P\) (real number).
  3. Circularity: Compute \(C=\frac{4\pi A}{P^2}\), where:
  • \(A\) is the component’s area;
  • \(P\) is the component’s perimeter;
  • \(C\) is the circularity.
  1. Degenerate case: If \(P=0\), consider \(C=0\) and directly classify the candidate as REJECTED.
  2. Classification: If \(C>C_{\text{limiar}}\), classify the candidate as ACCEPTED; otherwise, classify it as REJECTED.
  3. Rounding: Display the value of \(C\) with four decimal places.
  4. Output: For each candidate, print the value of \(C\) followed by the classification. At the end, print the total number of accepted candidates.

6.14.2.2 📌 Computational Constraints

  • Use the constant \(\pi\) from the language’s standard library (e.g., math.pi), without approximations.
  • The comparison must be performed using the full-precision value of \(C\), before rounding for display.
  • The acceptance criterion is strict (\(C>C_{\text{limiar}}\)).
  • If \(P=0\), the division must not be performed.

6.14.2.3 🧠 Theoretical Background

Circularity is a geometric descriptor defined by \(C=\frac{4\pi A}{P^2}\), where:

  • \(A\) is the component’s area;
  • \(P\) is the component’s perimeter;
  • \(C\) is the circularity.

For a perfect circle, \(C=1\). As the shape becomes more elongated or irregular, the perimeter grows faster than the area, reducing the value of \(C\).

Shape Approximate circularity Interpretation
Circle \(1{,}0000\) Circular shape.
Square \(0{,}7854\) Approximately compact shape.
Elongated or irregular shape \(C\ll1\) Low circularity.
\(P=0\) \(0\) (adopted convention) Degenerate contour.

Circularity is invariant to translation, rotation, and scaling, and it is widely used to distinguish approximately circular components from other shapes.

6.14.2.4 📦 Input and Output Specification (VPL)

Input:

  • Line 1: integer \(N\).
  • Line 2: real number \(C_{\text{limiar}}\).
  • Next \(N\) lines: area \(A\) (integer) and perimeter \(P\) (real), separated by a space.

Output:

  • One line for each candidate, in the format C ACCEPTED or C REJECTED, with \(C\) presented with four decimal places.
  • Last line: Total accepted: X.

6.14.2.5 📌 Examples

Input Output Observation
3
0.6
78 31.4
100 40
50 60		 0.9941 ACCEPTED
0.7854 ACCEPTED
0.1745 REJECTED
Total accepted: 2		 Approximately circular candidate, compact shape, and elongated shape.
1
0.9
10 0		 0.0000 REJECTED
Total accepted: 0		 Null perimeter: degenerate contour.
🎮 Simulator EP06_02: Marker Filter by Circularity C = 4πA / P²
Adjust the threshold and observe which candidates (disks, squares, and irregular shapes) survive the filter.
–
Figure 6.22: Simulator EP06_02: Marker Filter by Circularity 
%%writefile EP06_02.py
# Python code
Overwriting EP06_02.py
TestSuite("EP06_02.py").run()
✔️ EP06_02.cases already exists in casos/
📋 5 case(s) loaded from casos/EP06_02.cases

🔍 Testing Python: EP06_02.py
⚠️ EP06_02.py: Empty file (fewer than 3 lines). Tests skipped.