Defining surfaces in border string sequences representing a raster image

• US 6,310,970 B1
• Filed: 03/09/2000
• Issued: 10/30/2001
• Est. Priority Date: 06/24/1998
• Status: Expired due to Term

• Current Assignee: ColorCom, Ltd.
• Original Assignee: ColorCom, Ltd.
• Inventors: Doll, Joseph
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/523,920
• Time in Patent Office: 600 Days
• Field of Search: 382/163, 382/162, 382/164, 382/166, 382/241-243, 382/197, 382/199, 382/190, 382/203, 382/202, 382/173, 382/185, 382/232, 382/291, 382/206, 382/275, 358/1.3, 358/1.6, 375/240.22, 375/241, 345/441-443, 345/17, 345/23-26, 345/467, 345/433
• US Class Current: 382/163
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding

Abstract

An apparatus is disclosed for converting a raster image comprising a plurality of pixels into a plurality of data tags representing at least one shape in the raster image. The apparatus comprises a computer program, or an integrated circuit implementing the steps of the computer program, wherein the computer program comprises:

(a) a border definer for generating a border string sequence representing a color border in the raster image, wherein:

(b) the border string sequence comprises a plurality of surface strings; and

(c) a surface string comprises a receive slope and a send slope representing a slope of the border passing through a predetermined area of the raster image; and

(d) a surface string sequencer for converting the border string sequence into one or more surfaces, wherein a surface comprises one or more surface string sequences representing a section of the border string sequence.

Claims

1. An apparatus for generating a plurality of data tags representing at least one shape in a raster image, the apparatus comprising:

a system memory for storing steps of a computer program; and

a computer processor connected to the system memory for executing the steps of the computer program,

wherein the computer program comprises;

(a) a border definer for generating a border string sequence representing a color border in the raster image, wherein;

the border string sequence comprises a plurality of surface strings; and

a surface string comprises a receive slope and a send slope representing a slope of the border passing through a predetermined area of the raster image; and

(b) a surface string sequencer for converting the border string sequence into one or more surfaces, wherein a surface comprises one or more surface string sequences representing a section of the border string sequence.

2. The apparatus as recited in claim 1, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) a surface string sequence comprises less than four non-repeating surface strings.

3. The apparatus as recited in claim 1, wherein a surface begins when the receive and send slope of a surface string in the border string sequence forms an angle less than ninety degrees.

4. The apparatus as recited in claim 1, wherein a surface begins at the beginning of the border string sequence.

5. The apparatus as recited in claim 1, wherein a surface begins at the beginning of a non-axial line in the border string sequence, wherein a non-axial line can occur when pixels in the raster image form at least two plateaus.

6. The apparatus as recited in claim 1, wherein:

(a) a current surface is related to an adjacent surface when the current and adjacent surface form an angle of ninety degrees or more; and

(b) when the current surface is related to the adjacent surface, the current surface comprises a surface string sequence comprising a surface string in the adjacent surface.

7. The apparatus as recited in claim 6, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) the surface string in the adjacent surface is a non-repeating surface string.

8. An integrated circuit for generating a plurality of data tags representing at least one shape in a raster image, the integrated circuit comprising:

(a) a border definer for generating a border string sequence representing a color border in the raster image, wherein;

the border string sequence comprises a plurality of surface strings; and

a surface string comprises a receive slope and a send slope representing a slope of the border passing through a predetermined area of the raster image; and

(b) a surface string sequencer for converting the border string sequence into one or more surfaces, wherein a surface comprises one or more surface string sequences representing a section of the border string sequence.

9. The integrated circuit as recited in claim 8, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) a surface string sequence comprises less than four non-repeating surface strings.

10. The integrated circuit as recited in claim 8, wherein a surface begins when the receive and send slope of a surface string in the border string sequence forms an angle less than ninety degrees.

11. The integrated circuit as recited in claim 8, wherein a surface begins at the beginning of the border string sequence.

12. The integrated circuit as recited in claim 8, wherein a surface begins at the beginning of a non-axial line in the border string sequence, wherein a non-axial line can occur when pixels in the raster image form at least two plateaus.

13. The integrated circuit as recited in claim 8, wherein:

(a) a current surface is related to an adjacent surface when the current and adjacent surface form an angle of ninety degrees or more; and

(b) when the current surface is related to the adjacent surface, the current surface comprises a surface string sequence comprising a surface string in the adjacent surface.

14. The integrated circuit as recited in claim 13, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) the surface string in the adjacent surface is a non-repeating surface string.

15. A method of generating a plurality of data tags representing at least one shape in a raster image, the comprising the steps of:

(a) generating a border string sequence representing a color border in the raster image, wherein;

the border string sequence comprises a plurality of surface strings; and

a surface string comprises a receive slope and a send slope representing a slope of the border passing through a predetermined area of the raster image; and

(b) converting the border string sequence into one or more surfaces, wherein a surface comprises one or more surface string sequences representing a section of the border string sequence.

16. The method as recited in claim 15, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) a surface string sequence comprises less than four non-repeating surface strings.

17. The method as recited in claim 15, wherein a surface begins when the receive and send slope of a surface string in the border string sequence forms an angle less than ninety degrees.

18. The integrated circuit as recited in claim 15, wherein a surface begins at the beginning of the border string sequence.

19. The method as recited in claim 15, wherein a surface begins at the beginning of a non-axial line in the border string sequence, wherein a non-axial line can occur when pixels in the raster image form at least two plateaus.

20. The method as recited in claim 15, wherein:

(a) a current surface is related to an adjacent surface when the current and adjacent surface form an angle of ninety degrees or more; and

(b) when the current surface is related to the adjacent surface, the current surface comprises a surface string sequence comprising a surface string in the adjacent surface.

21. The method as recited in claim 20, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) the surface string in the adjacent surface is a non-repeating surface string.

22. A computer program embodied on a computer-readable medium for generating a plurality of data tags representing at least one shape in a raster image, the computer program comprising source code segments comprising:

(a) a border definer for generating a border string sequence representing a color border in the raster image, wherein;

the border string sequence comprises a plurality of surface strings; and

a surface string comprises a receive slope and a send slope representing a slope of the border passing through a predetermined area of the raster image; and

(b) a surface string sequencer for converting the border string sequence into one or more surfaces, wherein a surface comprises one or more surface string sequences representing a section of the border string sequence.

23. The computer program as recited in claim 22, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) a surface string sequence comprises less than four non-repeating surface strings.

24. The computer program as recited in claim 22, wherein a surface begins when the receive and send slope of a surface string in the border string sequence forms an angle less than ninety degrees.

25. The computer program as recited in claim 22, wherein a surface begins at the beginning of the border string sequence.

26. The computer program as recited in claim 22, wherein a surface begins at the beginning of a non-axial line in the border string sequence, wherein a non-axial line can occur when pixels in the raster image form at least two plateaus.

27. The computer program as recited in claim 22, wherein:

(a) a current surface is related to an adjacent surface when the current and adjacent surface form an angle of ninety degrees or more; and

(b) when the current surface is related to the adjacent surface, the current surface comprises a surface string sequence comprising a surface string in the adjacent surface.

28. The computer program as recited in claim 27, wherein:

(a) a surface string is selected from the set consisting of a repeating surface string and a non-repeating surface string;

(b) the receive and send slopes of a repeating surface string are equal;

(c) the receive and send slopes of a non-repeating surface string are not equal; and

(d) the surface string in the adjacent surface is a non-repeating surface string.