Image boundary correction by fractal processing

• US 5,982,386 A
• Filed: 04/01/1997
• Issued: 11/09/1999
• Est. Priority Date: 04/02/1996
• Status: Expired due to Fees

• Current Assignee: SCREEN Holdings Co., Ltd.
• Original Assignee: SCREEN Holdings Co., Ltd.
• Inventors: Fujimoto, Hiroki
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/834,716
• Time in Patent Office: 952 Days
• Field of Search: 345/441-443, 345/428-430
• US Class Current: 345/443
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 5/73 Deblurring; Sharpening
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

At least part of an image boundary is specified as a target boundary portion to be processed and is then subjected to fractal processing. This procedure gives a corrected image boundary. When one cycle of the fractal processing magnifies the target boundary portion by M times, the target boundary portion is contracted to 1/M^N (wherein N is an integer of not less than 1) prior to the fractal processing. The fractal processing is recursively executed by N times on the contracted target boundary portion.

Claims

1. A method of correcting an image boundary, said method comprising the steps of:

(a) providing an image mask data representing an image boundary to be used to define an image object;

(b) specifying only part of said image boundary as a target boundary portion to be processed;

(c) carrying out a fractal processing on said target boundary portion to enhance fractal dimensions of said target boundary portion, thereby obtaining a corrected image boundary; and

(d) carrying out a specific image processing on said image object while determining a shape of said image object by said corrected image boundary.

2. A method in accordance with claim 1, wherein

one cycle of said fractal processing magnifies said target boundary portion by a factor of M;

and wherein

said step (c) comprises the steps of;

contracting said target boundary portion to 1/M^N while maintaining the size of the non-target boundary portion of said image boundary, where N is an integer of at least 1; and

recursively executing the fractal processing by N times for said contracted target boundary portion; and

connecting said corrected target boundary portion after said fractal processing with said non-target boundary portion to obtain said corrected image boundary.

3. A method in accordance with claim 2, wherein said factor M is equal to 2.

4. A method in accordance with claim 1, wherein

said step (d) comprises the step of:

generating said image object having a plurality of uniform-density areas where each pair of said uniform-density areas are divided by said corrected boundary portion and filling said plurality of uniform-density areas with different densities, respectively.

5. A method in accordance with claim 1, wherein

said step (d) comprises the steps of

providing two image objects overlapping partly with each other across said image boundary;

and

reshaping two image objects by said corrected boundary to make said two image objects to contact each other across said corrected boundary.

6. A method in accordance with claim 1, wherein

said target boundary portion is a digital line consisting of a plurality of line segments each parallel to one of a plurality of coordinate axes;

and wherein

said fractal processing comprises the steps of;

converting digital line data representing the digital line to chain code data including a plurality of code words each selected from three basic code words representing a right turn, a straight progress, and a left turn, respectively;

transforming each code word included in the chain code data according to a predetermined transform rule into a code string including at least one code word, thereby generating transformed chain code data including a plurality of said code strings, wherein each code string after the transform is made so that a pre-selected one of a starting vector and a terminal vector in a series of vectors expressed by the code string after the transform at least partly overlaps a pre-selected one of a first-half vector and a second-half vector of a pair of vectors expressed by each code word before the transform; and

decoding the transformed chain code data to generate transformed digital line data representing a transformed digital line having a higher fractal dimension than that of said digital line.

7. A method in accordance with claim 6, wherein

said transform rule comprises a rule of substituting each of said three basic code words included in the chain code data with a code string according to three boundary conditions indicative of a right turn, a straight progress, and a left turn;

and wherein

said step of generating the transformed chain code data comprises the steps of;

(1) selecting one of the three boundary conditions with respect to each code word to be transformed; and

(2) transforming each code word to a code string according to the transform rule under the selected boundary condition.

8. A method in accordance with claim 7, further comprising the step of:

specifying a first selection probability for selecting one of the three boundary conditions; and

wherein

said step (2) comprises the step of;

(i) selecting one of the three boundary conditions according to the first selection probability.

9. A method in accordance with claim 8, wherein

the transform rule comprises a rule including a plurality of available code strings to be transformed from one code word under one boundary condition;

and wherein

said method further comprises the step of;

when said plurality of available code strings are to be transformed from one code word according to the transform rule, specifying a second selection probability for selecting one of the plurality of available code strings; and

wherein

said step (i) comprises the step of;

when said plurality of available code strings are to be transformed from one code word according to the transform rule, selecting one of the plurality of available code strings according to the second selection probability.

10. A method in accordance with claim 9, wherein said step of generating the transformed chain code data comprises the steps of:

maintaining a front-end code in the chain code data unchanged; and

adding a predetermined code word to an back-end of the transformed chain code data.

11. A method in accordance with claim 10, further comprising the step of:

recursively executing said step of generating the transformed chain code data by a desired times.

12. A method in accordance with claim 11, further comprising the steps of:

measuring fractal dimensions of fundamental lines which are transformed according to the fractal processing with various combinations of the number of repetitions of said step of generating the transformed chain code data and said first and second selection probabilities;

storing relationship between the measured fractal dimensions, the number of repetitions, and said first and second selection probabilities;

specifying the number of repetitions and a desired fractal dimension prior to said step of generating the transformed chain code data; and

setting the first and second selection probabilities prior to the step of generating the transformed chain code data so that the desired fractal dimension is be attained by the specified number of repetitions according to said relationship between the fractal dimension, the number of repetitions, and the first and second selection probabilities.

13. An apparatus for correcting an image boundary, said apparatus comprising:

means for providing an image mask data representing an image boundary to be used to define an image object;

extraction means for extracting only part of said image boundary as a target boundary portion to be processed;

boundary correction means for carrying out a fractal processing on said target boundary portion, thereby obtaining a corrected image boundary; and

means for carrying out a specific image processing on said image object while determining a share of said image object by said corrected image boundary.

14. A method of processing a digital line consisting of a plurality of line segments each parallel to one of a plurality of coordinate axes;

said method comprising the steps of;

converting digital line data representing the digital line to chain code data including a plurality of code words each selected from three basic code words representing a right turn, a straight progress, and a left turn, respectively;

transforming each code word included in the chain code data according to a predetermined transform rule into a code string including at least one code word, thereby generating transformed chain code data including a plurality of said code strings, wherein each code string after the transform is made so that a pre-selected one of a starting vector and a terminal vector in a series of vectors expressed by the code string after the transform at least partly overlaps a pre-selected one of a first-half vector and a second-half vector of a pair of vectors expressed by each code word before the transform; and

decoding the transformed chain code data to generate transformed digital line data representing a transformed digital line having a higher fractal dimension than that of said digital line.

15. An apparatus for processing a digital line consisting of a plurality of line segments each parallel to one of a plurality of coordinate axes;

said apparatus comprising;

coding means for converting digital line data representing the digital line to chain code data including a plurality of code words each selected from three basic code words representing a right turn, a straight progress, and a left turn, respectively;

transforming means for transforming each code word included in the chain code data according to a predetermined transform rule into a code string including at least one code word, thereby generating transformed chain code data including a plurality of said code strings, wherein each code string after the transform is made so that a pre-selected one of a starting vector and a terminal vector in a series of vectors expressed by the code string after the transform at least partly overlaps a pre-selected one of a first-half vector and a second-half vector of a pair of vectors expressed by each code word before the transform; and

decoding means for decoding the transformed chain code data to generate transformed digital line data representing a transformed digital line having a higher fractal dimension than that of said digital line.

16. A computer program product stored on a computer readable medium for correcting an image boundary, said computer program product comprising:

first program code for providing an image mask data representing an image boundary to be used to define an image object;

second program code for causing a computer to extract part of said image boundary as a target boundary portion to be processed;

third program code for causing said computer to carry out a fractal processing for said target boundary portion, thereby yielding a corrected image boundary; and

fourth program code for carrying out a specific image processing on said image object while determining a shape of said image object by said corrected image boundary.

17. A computer program product stored on a computer readable medium for processing a digital line consisting of a plurality of line segments each parallel to one of a plurality of coordinate axes;

said computer program product comprising;

first program code means for causing a computer to convert digital line data representing the digital line to chain code data including a plurality of code words each selected from three basic code words representing a right turn, a straight progress, and a left turn, respectively;

second program code means for causing the computer to transform each code word included in the chain code data according to a predetermined transform rule into a code string including at least one code word, thereby generating transformed chain code data including a plurality of said code strings, wherein each code string after the transform is made so that a pre-selected one of a starting vector and a terminal vector in a series of vectors expressed by the code string after the transform at least partly overlaps a pre-selected one of a first-half vector and a second-half vector of a pair of vectors expressed by each code word before the transform; and

third program code means for causing the computer to decode the transformed chain code data to generate transformed digital line data representing a transformed digital line having a higher fractal dimension than that of said digital line.