Digital Image Processing

Digital Image Processing Presentation by: Majid Nazeer

Comsats Institute of Information Technology, Islamabad.

Outlines • Matching Shape Numbers • String Matching • Syntactic Methods • Interpretations

Matching Shape Numbers • Let a and b denote shape numbers of closed boundaries represented by 4-directional chain codes. There two shapes have a degree of similarity k if s j (a) = s j (b), for j = 4,6,8,..., k s j (a) ≠ s j (b), for j = k + 2, k + 4,...

• where s indicates shape number and the subscript indicates order. • The distance between two shapes a and b defined as

1 D ( a, b) = k

• Direction numbers for 4-directional chain code, and 8directional chain code;

1

2 3

0

2

1

0

4

7

5 3

6

• Digital boundary with resampling grid superimposed

• All shapes of order 4, 6,and 8 Order6

Order4

Chain code: 0321 Difference : 3333 Shape no. : 3333

Chain code: 003221 Difference : 303303 Shape no. : 033033

Order8

Chain code: 00332211 Difference : 30303030 Shape no. : 03030303

Chain code:03032211 Difference :33133030 Shape no. :03033133

Chain code: 00032221 Difference : 30033003 Shape no. : 00330033

Advantages: 1.Matching Shape Numbers suits the processing structure simple graph, specially becomes by the line combination. 2. Can solve rotation of the shape. 3. Matching Shape Numbers most emphatically to the graph outline, Shape similarity also may completely overcome. 4.The Displacement question definitely may overcome, because of this method emphatically to the relative position but is not to the position.

Disadvantages : 1. It can not uses for a hollow structure. 2.Scaling is a shortcoming which needs to change, perhaps coordinates the alternative means. 3. Mirror problem. 4. The color is unable to recognize.

String Matching • String matching is the technique of finding approximate matches to a pattern in a string. • The closeness of a match is measured in terms of the number of primitive operations necessary to convert the string into an exact match. This number is called the edit distance. • The usual primitive operations are: – insertion – deletion – substitution

• Suppose that two region boundaries, a and b, are coded into strings denoted a1, a2, …, an and b1, b2, …,bm, respectively. • Let α represent the number of matches between the two strings, where a match occurs in the kth position if ak = bk . • The number of symbols that do not match is

β = max( a , b ) − α

• A simple measure of similarity between a and b is the ratio

α α R= = β max( a , b ) − α

• Strings are formed from the polygons by computing the interior angle, θ , between segments as each polygon was traversed clockwise. • Angles are coded into one of eight possible symbols, corresponding to 45o increments. α1 : 0 < θ ≤ 45o ; α 2 : 45o < θ ≤ 90o ;...

Syntactic Methods • Step1: Object class generation using a regular string grammar • For example: the srting of Fig. 12.26(c) is abbbbbc.

• Step 2: use of semantics (production rules)

• Step 3: automata as string recognizers

Thank You