Image processing using adjoining relationships between image parts

• US 6,577,777 B1
• Filed: 05/16/2000
• Issued: 06/10/2003
• Est. Priority Date: 10/11/1995
• Status: Expired due to Term

• Current Assignee: SCREEN Holdings Co., Ltd.
• Original Assignee: SCREEN Holdings Co., Ltd.
• Inventors: Hatada, Koji, Yoshino, Kimitoshi
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US09/572,484
• Time in Patent Office: 1,120 Days
• Field of Search: 382/284, 382/203, 382/204, 382/205, 382/199, 382/282, 345/435, 345/434, 345/431, 345/629, 345/630, 345/631, 345/619, 345/634, 707/527, 358/450, 358/453
• US Class Current: 382/284
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

The present invention carries out a desired image processing while using adjoining relationship between image parts. When each pair of image parts among a plurality of consecutive image parts drawn in a predefined drawing order have a difference in density value that is smaller than a threshold value and are located adjacent to one another, the consecutive image parts are recognized to constitute one combined image part. A desired image processing, such as trapping process, is carried out for the combined image part.

Claims

1. A method for processing image data of the type which includes a plurality of objects located in a predetermined area, each of said objects including a plurality of pixels and having an external, closed contour, said method comprising the steps of:

identifying a group of adjoining objects which should be processed as a single combined object, each object of said group adjoining at least one other object of said group to form a respective pairs of objects, a difference between an image density of each of said objects of said respective pair being greater than zero but less than a predetermined value;

image processing said group as a single combined object;

wherein said act of identifying comprises the acts of;

generating a bit map of said predetermined area, said bit map comprising a grid of pixels, each of said objects corresponding to a respective plurality of said pixels, each pixel of said bit map which corresponds to one or more of said objects being assigned a value associated with a respective one of its corresponding objects; and

identifying one or more pairs of adjoining objects as being part of said group by examining said values of said pixels in said bit map to determining which objects adjoin one another.

2. A method according to claim 1, wherein said act of image processing includes modifying said contours of said objects.

3. A method according to claim 2, wherein at least one of said plurality of objects which is not part of said group adjoins or overlaps said group and wherein said image processing is a trapping operation carried out between said at least one object and said group of objects.

4. A method according to claim 3, wherein said trapping operation treats the individual objects of said group as a single object for the purpose of determining the shape of a trap formed during said trapping operation.

5. A method according to claim 4, wherein said trapping operation treats individual objects of said group of objects as separate objects for the purpose of determining the color and density of respective segments of said trap.

6. A method according to claim 5, wherein said trap is formed along a boundary between said at least one object and said group of objects.

7. A method according to claim 2 wherein said act of identifying comprises the act of:

examining the relative image density of said adjoining objects.

8. A method according to claim 7, wherein said values of all of said pixels are examined.

9. A method according to claim 8, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

10. A method according to claim 7, wherein objects are determined to abut or overlap one another whenever said adjacent pixels have a different value.

11. A method according to claim 7, wherein when two or more of said objects overlap to define an area of overlap, said act of generating assigns a value to each pixel in said area of overlap according to an assigned hierarchy of said overlapping objects.

12. A method according to claim 11, wherein said assigned hierarchy is a function of which of said overlapping objects is the topmost object.

13. A method according to claim 12, wherein said hierarchy is assigned by a human operator.

14. A method according to claim 12, wherein each object is assigned a unique value indicative of its hierarchy and said value assigned to each pixel in said area of overlap is said value of said topmost object of said overlapping objects.

15. A method according to claim 7, further including the act of selecting a desired resolution of said pixels.

16. A method according to claim 15, wherein said act of selecting a desired resolution of said pixels is carried out by a human operator.

17. A method according to claim 7, wherein said act of generating includes an act of successively writing respective object bit maps of each of said objects into a bit map memory, each object bit map being made up of a plurality of pixels, all of said pixels of a respective object bit map being assigned a single value which is different than the values assigned to said pixels of the remaining said object bit maps, said object bit maps being read into said bit map memory in accordance with said assigned hierarchy, each of said pixels of a respective object bit map being placed in a respective memory location of said bit map memory which corresponds to the position of that pixel in said predetermined area, each time a new value is placed in a respective memory location it replaces any prior value stored in that location.

18. A method according to claim 17, wherein each of said object bit maps are generated and stored in one or more temporary memories before they are stored in said bit map memory.

19. A method according to claim 17, wherein said act of determining comprises the step of examining values of said pixels in said bit map memory.

20. A method according to claim 19, wherein said values of all of said pixels are examined during said determining step.

21. A method according to claim 20, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

22. A method according to claim 19, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

23. Apparatus for processing image data of the type which includes a plurality of objects located in a predetermined area, each of said objects including a plurality of pixels and having an external, closed contour, said apparatus comprising:

means for identifying a group of adjoining objects which should be processes as a single combined object, each object of said group adjoining at least one other object of said group to form respective pairs of objects, a difference between an image density of each of said objects of said pair being greater than zero but less than a predetermined value;

an image processor which processes said group as a single combined object; and

wherein said means for identifying;

generates a bit map of said predetermined area, said bit map comprising a grid of pixels, each of said objects corresponding to a respective plurality of said pixels, each pixel of said bit map which corresponds to one or more of said objects being assigned a value associated with a respective one of said objects;

identifies one or more pairs of adjoining objects as being part of said group by examining said values of said pixels in said bit map to determine which objects adjoin one another.

24. An apparatus according to claim 23, wherein said step of processing includes modifying said contours of said objects.

25. Apparatus according to claim 24, wherein at least one of said plurality of objects which is not part of said group adjoins or overlaps said group and wherein said image processor carries out a trapping operation between said at least one object and said group of objects.

26. Apparatus according to claim 25, wherein said trapping operation carried out by said image processor treats the individual objects of said group as a single object for the purpose of determining the shape of a trap formed during said trapping operation.

27. Apparatus according to claim 26, wherein said trapping operation carried out by said image processor treats individual objects of said group of objects as separate objects for the purpose of determining the color and density of respective segments of said trap.

28. Apparatus according to claim 27, wherein said trap is formed along a boundary between said at least one object and said group of objects.

29. Apparatus according to claim 24, wherein said means for identifying includes:

examining the relative image density of said adjoining objects.

30. Apparatus according to claim 29, wherein said means for identifying examines said values of all of said pixels.

31. Apparatus according to claim 30, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

32. Apparatus according to claim 29, wherein objects are determined to abut or overlap one another whenever said adjacent pixels have a different value.

33. Apparatus according to claim 29, wherein when two or more of said objects overlap to define an area of overlap, said means for identifying assigns a value to each pixel in said area of overlap according to an assigned hierarchy of said overlapping objects.

34. Apparatus according to claim 33, wherein said assigned hierarchy is a function of which of said overlapping objects is the topmost object.

35. Apparatus according to claim 34, further including means for enabling a human operator to select said assigned hierarchy.

36. Apparatus according to claim 28, further including means for enabling an operator to select a desired resolution of said pixels.

37. Apparatus according to claim 33, wherein said means for identifying generates said bit map of said predetermined area by:

successively writing each of said object bit maps into a bit map memory according to said assigned hierarchy, each of said pixels of a respective object bit map being placed in a respective memory location of said bit map memory which corresponds to the position of that pixel in said predetermined area, each time a new value is placed in a respective memory location it replaces said prior value stored in that location.

38. Apparatus according to claim 37, wherein said means for identifying determines that each object of said pair adjoins at least one other object in said group by examining values of said pixels in said bit map memory.

39. Apparatus according to claim 38, wherein said means for identifying examines said values of all of said pixels in said bit map memory.

40. Apparatus according to claim 39, wherein said means for identifying determines that objects adjoin one another whenever said adjacent pixels have a different value.

41. Apparatus according to claim 38, wherein said means for identifying determines that objects adjoin one another whenever said adjacent pixels have a different value.

42. A computer readable medium having a computer program stored thereon for determining an adjoining relationship between a plurality of objects located in a predetermined area, each of said objects including a plurality of pixels and having an external, closed contour;

said computer program, when executed in a CPU, being adapted to carry out a method comprising the steps of;

identifying a group of adjoining objects which should be processes as a single combined object, each object of said group adjoining at least one other object of the group to form respective pairs of objects, a difference between an image density of each of said objects of said pair being greater than zero but less than a predetermined value;

image processing said group as a single combined object; and

wherein said act of identifying comprises the acts of;

generating a bit map of said predetermined area, said bit map comprising a grid of pixels, each of said objects corresponding to a respective plurality of said pixels, each pixel of said bit map which corresponds to one or more of said objects being assigned a value associated with a respective one of its corresponding objects; and

identifying one or more pairs of adjoining objects as being part of said group by examining said values of said pixels in said bit map to determining which objects adjoin one another.

43. A computer readable medium according to claim 42, wherein said act of image processing includes modifying said contours of said objects.

44. A computer readable medium according to claim 43, wherein at least one of said objects located in said predetermined area is not part of said group but is adjacent to or overlaps said group and wherein said image processing is a trapping operation carried out between said at least one of said objects and said group of objects.

45. A computer readable medium according to claim 44, wherein said trapping operation treats the individual objects of said group as a single object for the purpose of determining the shape of a trap formed during said trapping operation.

46. A computer readable medium according to claim 45, wherein said trapping operation treats individual objects of said group of objects as separate objects for the purpose of determining the color and density of respective segments of said trap.

47. A computer readable medium according to claim 46, wherein said trap is formed along a boundary between said at least one of said objects and said group of objects.

48. A computer readable medium according to claim 43, wherein said act of identifying comprises the act of:

examining the relative image density of said adjoining objects.

49. A computer readable medium according to claim 48, wherein all of said values of all of said pixels are examined during said determining step.

50. A computer readable medium according to claim 49, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

51. A computer readable medium according to claim 48, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

52. A computer readable medium according to claim 48, wherein when objects in said predetermined area overlap, said generating step assigns a value to each pixel in said overlapping area of said objects according to an assigned hierarchy of said overlapping objects.

53. A computer readable medium according to claim 52, wherein said predetermined hierarchy is assigned as a function of which of said overlapping objects is the topmost object.

54. A computer readable medium according to claim 53, wherein said program is designed to permit said hierarchy to be assigned by a human operator.

55. A computer readable medium according to claim 54, wherein said computer program is designed to permit the resolution of said pixels to be selected by a human operator.

56. A computer readable medium according to claim 48, wherein said generating step includes the steps of:

creating a respective object bit map for each of said objects, each object bit map being made up of a plurality of pixels, all of said pixels of a respective object bit map being assigned a single value which is different than said value assigned to said pixels of the remaining object bit maps;

successively writing each of said object bit maps into a bit map memory according to said assigned hierarchy, each of said pixels of a respective object bit map being placed in a respective memory location of said bit map memory which corresponds to the position of that pixel in said predetermined area, each time a new value is placed in a respective pixel memory location it replaces said prior value stored in that location.

57. A computer readable medium according to claim 56, wherein said act of determining comprises the step of examining values of said pixels in said bit map memory.

58. A readable medium according to claim 57, wherein said values of all of said pixels are examined during said determining step.

59. A computer readable medium according to claim 58, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.

60. A computer readable medium according to claim 57, wherein objects are determined to adjoin one another whenever said adjacent pixels have a different value.