JPH0789376B2 - Digital contour coding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION <Industrial field of application> The present invention relates to a method for encoding a digital contour line in image data of a digital figure read from an input device such as a facsimile.

<Prior Art> Extracting a contour line, which is the outermost portion of a black pixel area in a digital figure read from a facsimile or the like, is extremely important as two-dimensional information for describing the characteristics of the digital figure. Become. At this time, a large amount of digital contour line data is stored in a limited storage device,
Alternatively, for transmission, it is necessary to encode the digital contour line data and compress the data amount.

As a coding method for such a digital contour line, the Freeman chain coding method shown in FIGS. 8A and 8B is conventionally known.

This method is centered on one pixel of the digital contour line,
Pixels are tracked in the eight directions of arrows 0 to 7 shown in FIG. This chain code is
Since one pixel forming the digital contour is represented by eight symbols, the number of coding bits per link (a set of two connected pixels) is 3 bits.

For example, encoding of a digital contour line as shown in FIG. 8 (b) is performed by using the start point coordinate p _{s as} “007010776545654544233221”.
Expressed as 2 ".

However, in such a chain coding method, when it is not necessary to faithfully describe a digital contour line, for example, when describing a contour line with few small bends, the digital contour line is coded pixel by pixel (3 However, the coding efficiency cannot be improved to 3 bits or less per link.

<Problems to be Solved by the Invention> A problem to be solved by the present invention is to improve coding efficiency when it is not necessary to faithfully describe a digital contour line. The purpose of the present invention is to realize a more effective digital contour coding method than the chain coding method.

<Means for Solving Problems> The outline of the present invention for solving the above problems is as follows.

An image memory unit in which image data of a digital figure is stored, a contour line extraction / encoding algorithm for this digital figure and a main memory unit for storing the result of this encoding, and a contour group extraction / encoding A method for encoding a digital contour line, which comprises an algorithm and a processor for executing a numerical operation, and which does not need to faithfully describe the contour line, including: (a) a main memory starting from one point of a digital figure. And (b) determining an extraction point based on a preset pixel extraction interval from the tracking points, and (c) setting the pixel extraction interval to n. When (≧ 2), 2 ^k-1 ≦
a step of obtaining a positive integer k satisfying n <2 ^k and setting a segment length d = k + 1 in the main memory section from this, (d) a difference vector between the current extraction point and the previous extraction point The step of obtaining and storing the X and Y components in the main memory unit as one segment with the number of bits corresponding to the segment length d determined by the value of the pixel extraction interval n, and (e) step (d) Repeat the process until the trace point returns to the starting point, and (f) set the data format of the coded sequence consisting of the coordinates of the starting point, the number of segments, the segment length and the X and Y components of the difference vector of each segment to the digital contour code. And a step of converting the information into encoded information.

<Operation> According to the digital contour line encoding method of the present invention, tracing is sequentially performed on a pixel-by-pixel basis, the extraction point is determined based on a preset pixel extraction interval, and the current extraction point and the previous extraction point are extracted. The difference vector with respect to the point is obtained, and its X and Y components are used as the coded information of the digital contour line.

<Example> An example of an apparatus suitable for implementing the method of the present invention is shown in FIG. 1 as a structural block diagram.

In the figure, 1 is an image memory unit for storing graphic data of a digital image read from an input device such as a facsimile, and 2 is a main memory unit for storing a digital contour line extraction / encoding algorithm and its encoding result. Three
Is a processor unit composed of a processor 3 ₁ for executing a numerical operation and a digital contour line extraction / encoding algorithm and a register group 3 ₂ for temporarily storing the result. The image memory unit 1, the main memory unit 2 and the processor unit 3 Are mutually connected to the system bus SB, and the processor unit 3 can access the image memory unit 1 and the main memory unit 2.

The object handled by the present invention is a digital contour line of a digital image in the image memory unit 1 as shown in FIG. 4, the X component (0 ≦ X ≦ M) from left to right of the screen, and Y from top to bottom of the screen. Each pixel has a component (0 ≦ Y ≦ N) and can be referred to by coordinates (X, Y). However, X, Y, M, N are non-negative integers.

Next, the principle of the encoding method of the present invention will be described with reference to FIGS. 5 (a) and 5 (b).

As shown in FIGS. 8 (a) and 8 (b), the conventional encoding method traces the digital contour line on a pixel-by-pixel basis and extracts and encodes it. However, the method of the present invention is shown in FIG. (A),
As shown in (b), pixels are tracked in pixel units, but extraction is performed based on a preset pixel extraction interval (P _s , P _1n , P _2n , ... P _l-1n ). Of the difference vector a _j (a ₁ , a ₂ , ..., a _l ) between the extraction point P _jn of P _jn and the previous extraction point P _j-1n, and this X, Y component (ΔX _j , ΔY _j ) ( 1 ≦ j ≦ l, P _0n = P _s )
Is used as encoded information.

The procedure (algorithm) of the digital contour coding method of the present invention will be described in detail below with reference to the flowchart of FIG.

(1) First, the image memory unit 1 is scanned to extract the black pixel point on the uppermost line and the leftmost side as one point on the contour line of the digital figure, and set it as the starting point P _s .

(2) The coordinate values (X _s , Y _s ) of the starting point P _s are stored in the registers RX _s and RY _s , respectively, and are also stored in the main memory unit 2.

(3) When the pixel sampling interval of a digital contour and n (≧ 2), stores the positive integer k that satisfies the ^{2 K-1 ≦ n <2} k determined, as the segment length d = k + 1 in the main memory section 2 To do.

(4) The contents of the registers RX _s and RY _s are set in the registers RX _a and RY _a , respectively.

(5) The initial value 0 is set in the register i.

(6) The initial value 0 is set in the register 1 for counting the number of segments.

(7) Set the initial value n-1 in the register CNTR. The value of n is the tracking point (pixel) extraction interval.

(8) When the point P _i (X _i , Y _i ) is the current tracking point on the contour line, the next tracking point P _{i + 1} is obtained and its coordinate value (X _{i + 1} ,
Y _{i + 1} ) is stored in registers RX and RY, respectively. This contour line extraction method includes a method using a 3 × 3 mask mentioned in the conventional example, a method using a 2 × 2 mask, and the like. Here, it is assumed that the contour line is extracted in the form of 8 connections. To do.

(9) Add 1 to the content of register i.

(10) By subtracting the contents of registers RX _s and RY _s from the contents of registers RX and RY, the distance D between tracking point P _{i + 1} and start point P _s
Calculate X and DY respectively.

(11) Check the values of DX and DY. If DX = DY = 0, {Y} proceeds to step (17), and if DX = DY = 0, {N} proceeds to step (12).

(12) Subtract 1 from the contents of register CNTR.

(13) Check the contents of register CNTR. If CNTR = 0, {N} repeats the operation from step (8),
When CNTR = 0, {Y} executes step (14).

(14) Subtract the contents of registers RX _a and RY _a that store the coordinate values of the previous extraction point from the contents of registers RX and RY that store the coordinate values of the current extraction point P _{i + 1.} , The difference vector a _i (ΔX, ΔY) between the current extraction point and the previous extraction point is obtained and stored in the main memory unit 2. Here, the calculated components ΔX and ΔY of the difference vector a _i are respectively stored in the main memory unit 2 as one segment with the number of bits corresponding to the segment length d calculated in three steps.

(15) The contents of the registers RX and RY in which the coordinate values P _{i + 1 of the} current extraction point are stored are set in the registers RX _a and RY _a , respectively.

(16) Add 1 to the contents of register l, and step (7)
Repeat the operation from.

On the other hand, in (11), if DX = DY = 0, {Y} means that the digital contour line is closed, and step (17) is executed.

(17) registers the start point coordinate value P _s is stored RX _s, RY _s
The contents of registers RX _a and RY _a , which store the coordinate values of the final extraction point, are subtracted from the contents of to obtain the X and Y components of the difference vector from the last extraction point, and the main memory section Store in 1. However, at this time, RX = RX
_s , RY = RY _s .

(18) Add 1 to the contents of register l.

(19) The content of the register 1 is stored in the main memory unit 2 as the number of segments.

(20) Operation end (END).

The method of the present invention is executed according to the above procedure.

In this way, the data format of the coded sequence obtained by the method of the present invention is as shown in FIG.

The coded sequence has the starting point coordinate value P _s (X _s , X _s ,
Y _s ), the number of segments l, the segment length d (= k + 1), and the difference vectors (ΔX _j , ΔY _j ) from the 1st to the 1st (j =
1,2, ..., l). Further, the difference vector (ΔX _j , ΔY _j ) is expressed in the two's complement format.

Here, the coded bit number representing the starting point coordinate value P _s is C _s , the coded bit number representing the segment number l is Cl, the coded bit number representing the segment length d is Cd, and the difference vector (ΔX _j , ΔY _j ), where C _Δ is the number of coding bits representing the digital contour line consisting of 1 segment according to the method of the present invention, C = C _S + C _l + C _d + C _Δ · l It is represented by.

Also, since C _Δ = 2d, C = C _S + C _l + C _d + 2d · l. Generally, since C _S + C _l + C _d << 2d · l, C≈2d · l.

On the other hand, if the total number of pixels constituting the digital contour line is _L and the number of coded bits representing _L is C _L , the number of coded bits C _f of the conventional chain coding method is C _f = C _S + C _L + 3L It is expressed, and in general, C _S + C _L << 3L, so C _f ≈3L.

Here, since 1≈L / n (2 ^k−1 ≦ n <2 ^k , d = k + 1), the chain coding method and the coding bit ratio C / C _f according to the method of the present invention are C / C _f ≈2d · l / 3L = 2d / 3n = 2 (k + 1) / 3n.

For example, when n = 3, since d = 3, C / C _f = 2/3, and when the chain coding method and the coding method according to the present invention are compared, the number of coding bits is 2 /. It can be compressed to about 3.

That is, the number of coded bits per link can be compressed from the conventionally required 3 bits to about 2 bits.

6 (a) and 6 (b) show an example of extraction in which the difference vector is obtained by actually using the method of the present invention.

Fig. 6 (a) shows the starting point P for the digital contour line.
_The extraction interval n = 3 from _s (X _s , Y _s ) and the extraction points P ₁₃ , P ₂₃ ,
…, P ₁₁₃ is obtained, and the difference vector a ₁ ,
This is an example in which a ₂ , ..., A ₁₂ are obtained.

The values of the components of each difference vector obtained in FIG. 6 (a) are stored in the main memory unit 2 in the data format shown in FIG. 6 (b).

That is, the starting point coordinate value P _s (X _s , Y _s ), the number of segments l = 12,
Segment length d = 3, difference vector a _j (j = 1,2, ..., 1
It is composed of the values of the X and Y components of 2). However, the value of each component of the difference vector is represented in 2's complement format.

Next, FIG. 7 shows the result of decoding according to this coding information.

Decoding is performed by using the starting point coordinates P _s (X _s , Y _s ) as a starting point and calculating the X and Y components of the difference vector a _j from the segment length d by the number of segments l.
However, it is only necessary to sequentially cut out, calculate the approximate vector from the difference vector each time, and reproduce the line figure corresponding to this approximate vector as the contour line.

In FIG. 7, each block is reproduced as a contour line, a block indicated by a dotted line represents a pixel of the original figure, and a shaded block represents a pixel displaced from the original figure.

As described above, according to the method of the present invention, the number of coding bits can be reduced when it is not necessary to faithfully describe a digital contour line.

<Effects of the Invention> According to the digital contour line encoding method of the present invention, tracking is sequentially performed pixel by pixel, the extraction point is determined based on a preset pixel extraction interval, and the current extraction point and the previous extraction point are determined. Since the X and Y components of the difference vector with respect to the extraction point are obtained and used as the coding information of the digital contour line, the coding efficiency can be improved when it is not necessary to faithfully describe the digital contour line.

According to the present invention, the segment length d = k + 1 is determined by obtaining the integer k that satisfies 2 ^{k −1} ≦ n <2 ^k from the pixel extraction interval n.
Since each of the X and Y components of the difference vector is stored with the bit length d, the length of the data format of the encoded string determined by the value d can be the encoded information corresponding to the pixel extraction interval n, A coding method having higher coding efficiency than the conventional chain coding method can be realized.

Further, if the pixel extraction interval n is increased, the original digital contour line can be roughly approximated, and if the pixel extraction interval n is decreased, the original digital contour line can be finely approximated. In this way, it is possible to realize the encoding method using the difference vector according to the complexity of the digital contour line or the desired degree of approximation.

For example, if the pixel extraction interval when tracking pixels is 3, the number of bits per link (set of two connected pixels) can be compressed from 3 bits to about 2 bits.

The decoding can be easily performed by reproducing the line figure corresponding to the approximate vector from the information of the starting point coordinates, the number of segments, the segment length, and the difference vector.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an apparatus for carrying out the method for coding a digital contour line according to the present invention, and FIG. 2 is a flow chart showing a process procedure (algorithm) of the method for coding a digital contour line according to the present invention. FIG. 3 is a diagram showing the format of data obtained by the method of the present invention, FIG.
The figure shows a figure which is a target of the method of the present invention, FIGS. 5 (a) and 5 (b) are diagrams for explaining the principle of the method of the present invention, and FIGS. 6 (a) and 6 (b) are FIG. 7 is a diagram when the method of the present invention is applied to an actual figure, FIG. 7 is a diagram showing a result of decoding using data obtained by the method of the present invention, and FIG.
(A), (b) is a figure for demonstrating the conventional chain encoding method. 1 ... Image memory unit, 2 ... Main memory unit, 3 ... Processor unit, 3 ₁ ... Processor, 3 ₂ ... Register group.

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Internal reference number FI technical display location G06F 15/66 410

Claims (1)

[Claims] 1. An image memory unit in which image data of a digital figure is stored, a contour line extraction / encoding algorithm for the digital figure, a main memory unit for storing a result of the encoding, and a register group. A method of encoding a digital contour line, comprising: a contour line extraction / encoding algorithm and a processor unit that executes a numerical operation, wherein the contour line does not have to be described faithfully. Storing one point as a starting point in the main memory unit and sequentially performing tracking on a pixel-by-pixel basis; and (b) determining an extraction point from the tracking points based on a preset pixel extraction interval, (C) When the pixel extraction interval is n (≧ 2), 2 ^k−1 ≦
a step of obtaining a positive integer k satisfying n <2 ^k and setting a segment length d = k + 1 in the main memory section from this, (d) a difference vector between the current extraction point and the previous extraction point And storing the obtained X and Y components in the main memory unit as one segment with the number of bits corresponding to the segment length d determined by the value of the pixel extraction interval n, and (e) the step (e). D) repeating the trace point until the trace point returns to the starting point, and (f) the data of the encoded sequence consisting of the coordinates of the starting point, the number of the segments, the segment length, and the X and Y components of the difference vector of each segment. And a step of using a format as coding information of a digital contour line.