Vectorizing method

• US 5,007,098 A
• Filed: 12/30/1988
• Issued: 04/09/1991
• Est. Priority Date: 12/30/1988
• Status: Expired due to Term

• Current Assignee: YOZAN, Inc.
• Original Assignee: Ezel, Inc.
• Inventors: Kumagai, Ryohei
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/292,309
• Time in Patent Office: 830 Days
• Field of Search: 382/21, 382/22, 382/25, 382/60, 382/56
• US Class Current: 382/185
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding

Abstract

A vectorizing method generates an original train of codes for specifying boundary pixels. A revised train of codes is generated solely from the original codes. The revised train may includes points omitted from the original train. Vector points defining boundaries are selected from the revised train of codes.

Claims

1. A vectorizing method comprising the steps of:

(a) generating an original train of codes, the values of said codes specifying boundary pixels of a configuration;

(b) identifying a pattern of code values in said original train, said pattern indicating a sequence of codes to be modified;

(c) generating a revised train of codes by modifying code values of said indicated sequence; and

(d) extracting vector points defining the borders of said configuration from said revised train of codes.

2. A vectorizing method according to claim 1 wherein said codes are Freeman'"'"'s chain codes.

3. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k2 in a chain code train of "k1, k2, k3" included in said original train of codes when k2≠

k1-1.

4. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k2, k3" included in said original train of codes when k2=k1-1.

5. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k2 in a chain code train of "k1, k1, . . . , k1, k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, k2≠

k1-1.

6. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k1, . . . , k1, k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, k2=k1-1.

7. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to the first chain code k2 in a chain code train of "k1, k2, k2, . . . , k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, and k2≠

k1-1.

8. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k2, k2, . . . , k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, and k2=k1-1.

9. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to the first chain code of k2 in a chain code train "k1, k1, . . . , k1, k2, k2, . . . , k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1.

10. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting pixels corresponding to the first chain code K in the first and last occurrence of a repeating chain code combination when a chain code combination of "k, k, . . . , k, k-1" is repeatedly generated in said original train of codes.

11. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting pixels corresponding to chain code k+1 in the first and last occurrence of a repeating chain code combination when a chain code combination of "k, k, . . . , k, k+1" is repeatedly generated in said original train of codes.

12. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k2 in a chain code train of "k1, k2, k3" included in said original train of codes when k2≠

k1+1.

13. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k2, k3" included in said original train of codes when k2≠

k1+1.

14. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k2 in a chain code train of "k1, k1, . . . , k1, k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1 and k2≠

k1+1.

15. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k1, . . . , k1, k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1 and k2≠

k1+1.

16. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to the first chain code k2 in a chain code train of "k1, k2, k2, . . . , k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, k2=k1+1.

17. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting a pixel corresponding to chain code k3 in a chain code train of "k1, k2, k2, . . . , k2, k3" included in said original train of codes when k1≠

k2, k2≠

k3, k3≠

k1, k2=k1+1.

18. A vectorizing method according to claim 2, wherein the step of extracting vector points includes a step of extracting pixels corresponding to chain code k+1 in the first and last occurrence of a repeating chain code combination when a chain code combination of "k, k, . . . , k, k+1" is repeatedly generated in said original train of codes.

19. A vectorizing method in clockwise direction according to claim 2, wherein the step of extracting vector points includes a step of extracting pixels corresponding to chain code k+1 in the first and last occurrence of a repeating chain code combination when a chain code combination of "k, k, . . . , k, k-1" is repeatedly generated in said original train of codes.

20. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "076" included in said original train of codes to "0066".

21. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "210" included in said original train of codes to "2200".

22. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "654" included in said original train of codes to "6644".

23. A vectorizing method in anticlockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "432" included in said original train of codes to "4422".

24. A vectorizing method in clockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "670" included in said original train of codes to "6600".

25. A vectorizing method in clockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "012" included in said original train of codes to "0022".

26. A vectorizing method in clockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "456" included in said original train of codes to "4466".

27. A vectorizing method in clockwise direction according to claim 2, wherein the step of generating a revised train of codes includes a step of changing a combination of chain codes "234" included in said original train of codes to "2244".

28. A vectorizing method according to claim 1, wherein the step of generating an original train of codes includes steps of:

generating an original train of codes for an outer boundary in a first directional rotation around the configuration; and

generating an original train of codes for an inner boundary of the configuration in an opposite rotational direction to that of outer boundary.

29. A vectorizing method according to claim 1, wherein the step of generating an original train of codes includes a step of judging a pixel to determine whether it is the start point of said original train of codes by evaluating its neighbor pixels.

30. A vectorizing method according to claim 29, wherein the step of judging a pixel includes a step of defining a boundary pixel with neither upper nor left neighbors as said start point of said original train of codes on the outer boundary, when a scan line advances rightwardly and is generated after upper scan lines.

31. A vectorizing method according to claim 29, wherein the step of judging a pixel includes a step of defining a boundary pixel with a left neighbor but without a lower neighbor as said start point of said original train of codes on the inner boundary, when a scan line advances rightwardly and is generated after upper scan lines.

32. A vectorizing method according to claim 1, wherein the step of generating an original train of codes includes steps of:

generating codes according to rotational direction around the configuration; and

searching boundary pixels next to a pixel to be given a code in the same rotational direction as the direction of generation of the original train of codes.

33. A vectorizing method according to claim 32, wherein:

the train of codes are Freeman'"'"'s chain codes;

the pixel to be given a chain code is a direction k from the previous pixel; and

said searching step begins from the direction (k-1) when k is an even number.

34. A vectorizing method according to claim 32, wherein:

the train of codes are Freeman'"'"'s chain codes;

the pixel to be given a chain code is a direction k from the previous pixel; and

said searching step begins from the direction (k-2) when k is an odd number.

35. A vectorizing method according to claim 1 wherein the step of generating a revised train includes a step of identifying a string of at least one code in the original train to be modified based on codes in the original train on both sides string to be modified.

36. A vectorizing method according to claim 1 wherein the step of generating a revised train of codes includes a step of adding a code corresponding to a pixel not represented in the original code train.

37. A vectorizing method according to claim 36 wherein the step of adding a code includes a step of identifying the location in the original chain where a code is to be added based on codes in the original train of codes on both sides of the location.

38. A vectorizing method according to claim 36 wherein a code in the original train is changed to be compatible with an added code.

39. A vectorizing method according to claim 1 wherein the step of extracting vector points includes a step of defining endpoints of substantially straight segments in the boundary of the configuration.