JPS6211389B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a feature point extraction device for pattern recognition, and more particularly to a device for detecting element starting points of elements included in a pattern.

In pattern recognition, when tracing the contours of elements included in a pattern to obtain pattern information, the following methods have conventionally been used.

The starting point for tracing is the point on the pattern that is first detected by scanning the surface containing the pattern.The traced point is traced while marking the traced point to distinguish it from the untraced point. When returns to the starting point of the trace, the tracing from that starting point ends. Next, scan the surface containing the pattern to check if there is a point that has not been traced, and if a point that has not been traced is detected, repeat the above tracing process using that point as a starting point, and once the tracing is finished, scan the surface containing the pattern again. Scan and repeat until no untraced points are detected.

In this method, since the starting point of the trace has not been detected in advance, it is necessary to mark traced points on the pattern while tracing to distinguish them from untraced points. Therefore, it is necessary to scan the surface including the pattern until there are no untraced points, which takes a lot of time. However, if the starting point of the trace is detected first, it is only necessary to start tracing from the detected starting point of the trace, so there is no need to mark the traced point on the pattern, and there is no need to mark the traced point. There is no need to scan to Also,
When tracing a binary pattern whose line width is 1 bit for feature extraction, the starting point of the trace can be extracted using a mask, but the starting point of a loop pattern cannot be detected.

For example, in the binary pattern shown in Figure 1 (“0” is represented by a blank space), it becomes the starting point of the trace.
Although T ₁ and T ₂ can be detected using the end point/branch point detection mask shown in FIG. 2, the starting points LP ₁ and LP ₂ for tracing the loop cannot be detected. In addition, Figure 2a
-d are for detecting end points, and e-p in Fig. 2 are examples of masks for detecting branch points, A+B+C=1, C+D+E=
1, E+F+G=1, G+H+A=1, +
represents the logical operation OR.

An object of the present invention is to detect each trace starting point for each binary pattern in a short time by extracting one point for each element while detecting the connection of patterns without scanning the surface containing the pattern many times. Another object of the present invention is to provide an apparatus for detecting the starting point of an element, and furthermore, to provide an apparatus for detecting the starting point of a loop element that cannot be detected by a mask when the pattern is a binary pattern with a width of 1 bit.

According to the present invention, a pattern memory stores binary patterns of "0" and "1" in a matrix, and "1" changes from "0" to "1" in each column sequentially obtained from the pattern memory. ” and a position address B of “0” that changes from “1” to “0” after detection of A, as a set of run length data A and B; A connected block is used as an element, and the run length data obtained by the run length detection means is used as a partial element, and the connection relationship between the partial element and the partial element one row before in the detection order is checked and a label is created based on the connection relationship. and a partial element connection relationship processing means that receives the data obtained by the run length detection means and stores run length data C and D that are not connected to the run length data of the previous column, by the partial element connection relationship processing means. a starting point coordinate storage means for a partial element that stores starting point coordinates of a partial element whose row coordinate is C of the data and whose column coordinate is the current column address; A pattern element starting point detecting device is obtained which is constituted by an element starting point processing means for extracting the starting point of an element from the connection relationship and the starting point position of the partial element.

Further, according to the present invention, there is provided a pattern memory that stores binary patterns of "0" and "1" with a line width of 1 bit, and end points and branch points of the pattern in the pattern memory are extracted as feature points and their positions are Feature point detection means for storing addresses, and "0" to "1" in each column taken out from the pattern memory.
run length detection means for storing as a set of run length data A, B a position address A of "1" which changes to "1" and a position address B of "0" which changes from "1" to "0" after detection of A; A connected block of value patterns is used as an element, data obtained by the run length detection means is used as a partial element, and the connection relationship between the partial element and the partial element one row before in the detection order is checked and the connection relationship is determined. a partial element connection relation processing means for assigning a label to and storing a partial element; and whether the feature point position address obtained by the feature point detection means is included in the partial element of the run length data obtained by the run length detection means. a partial element feature point inclusion relation processing means for detecting and storing;
After receiving the data obtained by the run-length detection means, the run-length data C and D that are not connected to the run-length data one scanning row before are set as the first partial elements of the label given by the partial element connection relation processing means, and the data are starting point coordinate storage means for a partial element that stores starting point coordinates of a partial element in which C is a row coordinate and the current column address is a column coordinate; the partial element coupling relationship, the partial element feature point inclusion relationship, and the part; A pattern element starting point detection device is obtained, which includes an element starting point processing means for extracting an element starting point of an element that does not include a feature point as a loop starting point from the starting point position of the element.

The present invention will be described below with reference to drawings showing embodiments.

FIG. 3 is a block diagram showing the relationship between each memory to explain the element detection means using run-length data used in the present invention. In the figure, 1 is a binary pattern memory, 2 is a run-length memory,
3 is label memory, 4 is label counter, 5
is an associative relational memory.

In FIG. 4, a is an example of the contents of the binary pattern memory in FIG. 3, b is the run length memory in FIG. 3, c is the label memory in FIG.
d indicates a change in the contents of the connection relationship memory in FIG. 3, and e indicates a change in the contents of the label counter in FIG. 3. Each number on the left side of FIG. 4 represents a memory address.

Figure 4 a shows the result of creating a binary pattern with points that belong to the pattern as “1” and points that do not belong as “0”.
is left blank.

Scanning in the direction of the arrow is performed in numerical order starting from the smallest number given above FIG. 4a.

Address positions A and A attached to the left side of the diagram where the signal changes from "0" to "1" by scanning Figure 4 a
After detection, the address position B attached to the left side of the diagram of "0" changing from "1" to "0" is stored as run length data A, B in the run length memory for one scanning column.

FIG. 4b shows changes in the contents of the run-length memory corresponding to one scanning line. Check the connection relationship between run-length data A, B (B>A) of one scan row and run-length data C, D (D>C) of the previous scan row that has already been labeled. _The minimum value l= _min ( _{l1 ,}
l ₂ ,...l _o ) are the labels of run-length data A and B.

The conditions for being connected are (1) CA and AD (2) CB and BD (3) A<C and D<B (1), (2), or (3).

If there is no connected run length data, the contents of the label counter, which increases by one at that time, are given as the label.

FIG. 4c shows changes in the contents of the memory storing the labels when the labels are attached corresponding to the run length data of FIG. 4b.

FIG. 4e shows changes in the value of the label counter corresponding to the columns.

Here, the label counter is cleared at the beginning of a scan, and the run length memory and label memory are cleared at the beginning of each scan.

Generally, with a label, lm=min (l ₁ , l ₂ ,...l _o )
When finding n≧2, it indicates that different subelements are merging, and when n=l, it indicates that the subelements are continuous "1". For example, if n = 2, label l ₁ partial element and label
This means that the subelements of l ₂ are connected. Therefore, the relationship between the subelements of "1" is l _n = min (l ₁ , l ₂ , ... l _i , l _j ... l _o ) If l _n ≠ l _i , l _n ≠ l _j , the label l _i The "1" subelement of is connected to the "1" subelement of label l _j via the subelement of label l _n . here
l ₁ , l ₂ , ... _lo are the connected label values arranged in the order of detection.

FIG. 4d shows changes in the contents of the memory indicating the connection relationship of sub-elements of "1" in correspondence with the scanning rows. Associative relationship memory is expected to occur “1”
Prepare a capacity equal to or greater than the number of subelements in , and access the contents using label 1 as an address.
It is assumed that the contents are updated for each scan column.

Before scanning a pattern, the connection relationship memory is cleared, and when a label is generated, label 1 is written in the connection relationship memory specified by label 1.

For example, run length data 3 and 6 in the run length memory at address 1 in FIG. 4b obtained by scanning the 6th column in FIG. Since there is no connection with the length data, the value of the label counter increases by 1 to 2, and label 2 is written to the label memory location c in Figure 4, which is the same address as address 1 in the run-length memory, and as shown in Figure 4. d
As shown in the sixth column, label 2 is written to the connection relationship memory using label value 2 as an address.

When a combination of subelements is detected, the label l _i
The label l _n is written in the connection relationship memory specified by , and it is assumed that the partial element "1" of the label l _n is thereby connected to the partial element "1" of the rail l _i . For example, the run length data 7, 12 at address 1 in the 10th column in FIG. 4b obtained by scanning the 10th column in FIG. Label value 3 = based on the label attached to the run length data, that is, the label memory values 4 and 3 in the 9th column of Figure 4 c.
min (4, 3), and the label value 3 is written to the same label memory location as address 1 of the run-length memory shown in the 10th column of Figure 4c, and the label value 3 is written in the 10th column of Figure 4d. As shown, label value 3 is written to the connection relationship memory location with label 4 as the address, and as a result, the partial element of label 3 is combined with the partial element of label 4.

Processing of connection relationships between subelements is performed until the end of the entire scan. When the scanning of the pattern shown in Figure 4a is completed, the connection relation memory is 1,
2, 3, 3. From now on, partial element 1,
2 and 3 correspond to partial elements 1, 2, and 3, respectively, and partial element 4
It can be seen that is connected to partial element 3. Therefore, element 1 is derived from subelement 1, and element 2 is derived from subelement 2.
Therefore, element 3 consists of partial element 3 and partial element 4.

The circuit becomes simpler if the starting point of an element is the first point detected as an element.

The starting point of a partial element is the first point when a new partial element is detected, that is, the run length data E, which is not connected to the run length data of one scan row.
When F is detected, E is the row position and the scan column is the column position, and based on the starting point of the subelement and the connection relationship between the subelements, the starting point of the subelement that is not connected to other subelements. Let be the starting point of the element.

FIG. 5 is a diagram showing an embodiment of detecting the element starting point of an element included in a pattern of the present invention, in which the binary pattern memory 1, the address generation circuit 6, the partial element connection relation processing unit 7, and the element processing unit 8 , a connection relation storage section 9 , a partial element starting point coordinate memory 10 , and a run length detection section 11 .

Note that the control section is not shown.

The address generation circuit 6 has counters 610 and 620.
This is a circuit that generates an address to access the binary pattern memory 1. Initially, both are cleared, and the output of the counter 610 generates the address corresponding to the column, and the output of the counter 620 generates the address corresponding to the row. do. The counter 620 is cleared by the signal S-181 on the line 181 (hereinafter, the signal on the line L will be expressed as the signal SL) from the control section every time the counter 610 is incremented by one.

The run length detection section 11 includes a flip-flop 120 and registers 110, 130, 140.
It consists of AND gates 160 and 170, an OR gate 180, and an inverter 150.

The signal S-181 from the control section is sent to the OR gate 18
0, the output signal S-121 of the flip-flop 120 connected to the OR gate 180 is set to "1", and the output signal S-122 is set to "0".

When an address is generated by the address generation circuit 6, the binary pattern memory 1 is accessed, and the memory value of the specified address is set in the register 110. When the signal S-121 is "1", the register 11 is set with the contents of the binary pattern memory 1.
When the output signal S-111 of 0 becomes “1”, AND
The output signal S-161 of the gate 160 becomes "1", and the counter 62 indicating the row position of the address is sent to the register 130 which uses the signal S-161 as a set signal.
An output signal S-621 of 0 is set. Further, the signal S-161 is input to the flip-flop 120, and the output signal S-122 is set to "1" and the output signal S-121 is set to "0". When the value of the counter 620 increases and the output signal S-111 of the register 110 becomes "0", the output of the inverter 150 becomes "1",
AND with the output signal of the inverter 150 and the output signal S-122 of the flip-flop 120 as inputs
The output signal S-171 of the gate 170 becomes "1", and the register 140 which uses the signal S-171 as a set signal is set to the position where the binary pattern memory 1 becomes "0", that is, the output signal S-621 of the counter 620.
is set. Furthermore, the output signal S-171 of "1" is input to the OR gate 180, which changes the output signal S-121 of the flip-flop 120 to "1",
- Change 122 to “0” and return to original. counter 6
The value of 20 is increased and the above process is repeated, and when the value of the counter 620 crosses the value corresponding to the last row position, the counter 610 is incremented by 1, and the counter 620 is set by the signal S-181 from the control section. cleared.

Therefore, the signal S-171 becomes "1" every time one run length data is detected, and the value of the register 130 is at the "1" position where the value changes from "0" to "1" in one row of the binary pattern memory 1. A, the value of the register 140 represents the position B of "0" which changes to "0" after A is detected in one row.

The partial element connection relation processing unit 7 includes a run length memory 2 that stores run length data of the accessed column, a label memory 3 that stores the label corresponding to the run length data of the accessed column, and a label counter. 4, a run length memory 25 that stores run length data of the previous row, a label memory 35 that stores a label corresponding to the run length data of the previous row, a coupling relationship detection circuit 45, registers 200, 250,
260, 280, 310, 350 and counter 2
20, 300, selection circuits 230, 290, comparison circuit 270, and register 240 to which the maximum label value (for example, 63 in decimal notation for a 6-bit register) is set.

When a set of run length data is detected by the run length detection section 11, the counter 220 is started by the signal S-171, and the counter 220 is started by the signal S-1 from the control section.
The value of counter 300 reset at 81 is +1
be done.

The run length memory 2 uses the output signal S-301 of the counter 300 as an address, and the register 130
and 140, output signals S-131 and S-141, that is, values representing run length data are stored.

The label memory 3 stores a signal S-232 in which a label value to be added to the run-length data is output using the signal S-301 as an address.

Run length memory 25 and label memory 35
stores the data of the previous column, and the run length memory 25 stores the output signal S- of the counter 220.
221 is read as the address, and register 2 is read out.
50, and the label memory 35 receives the signal S.
-221 is read into the register 350 as the address.

The coupling relationship detection circuit 45 detects the obtained run length data signals S-131, S-141 and the run length data signals S-251, S-25 of the previous column.
2 satisfies the coupling conditions (1), (2), or (3), and if it is satisfied, "1" is output to line 451 and sent to the control section. “1” is output to the line 452 when the data is not combined with any of the data in the run length memory 25, and the label counter 4
is +1. Here, the label counter is initially cleared.

The counter 220 is started by the signal S-171 and increases by one each time the signal S-222 from the control section is sent.

The label memory 35 uses the output signal S-221 of the counter 220 as an address, and uses the signal S-45 as an address.
A label corresponding to the run length data combined under 1 is set in the register 350. Further, the register 260 stores all values set in the register 350, that is, label values attached to connected run length data. Here, the register 260 is cleared before obtaining the label of each run length data.

The maximum value is set in the register 240, and the selection circuit 290 receives the line 291 from the control section.
The control signal S-291-1 outputs the output signal of the register 240, and the control signal S-2 of the line 291 outputs the output signal of the register 240.
91-2 outputs signal S-271. Hereinafter, the Nth control signal on line L will be expressed as S--L--N.

When labeling the obtained run length data, first generate the signal S-291-1,
Set the maximum label value in register 280. Next, when the contents of the label memory 35 are read into the register 350 and the label value attached to the combined run length data is set, the comparison circuit 270 outputs the signal S-281 and the signal S-351.
The signal with the smaller value is sent to line 271.
Output to. After that, the control signal S-
When the signal S-291-2 is generated, the signal S-271 is input to the register 280, so that the minimum value of the level values added to the combined run-length data is set in the register 280. Therefore register 280
If the value is the maximum value, the value of the label counter 4 becomes the label, and if it is not the maximum value, the value of the register 280 becomes the label to be attached to the run length data.

The selection circuit 230 receives the control signal S-2 from the control section.
31 sends the signal S-271 from register 280.
Or signal S-401 from label counter 4
is selected, and the signal S-232 is output as a label value to be attached to the run length data.

Registers 200 and 310 are buffer registers for writing values into the run-length memory 25 and label memory 35. After labeling a row of run-length data, the contents of memories 2 and 3 are transferred via registers 200 and 310. be done.

The starting point of a subelement is the first point when a new subelement is detected, and a new subelement is detected when run length data that is not connected to the run length data of the previous column is detected, and the coordinates of the starting point are the row coordinates. From the run-length data as column coordinates, the run-length data is obtained from the column for which you are seeking.

Therefore, the partial element starting point coordinate memory 10 receives the signal S-23 representing the label value of the run length data.
2 is the address, and the signal S- is “1” when it is not combined with any of the run length data of the previous column.
452 as a set signal, and the output signal S-131 of the register 130 in which the position address of "1" of the run length data is set as the row position.
Column address signal S-611 of address generation circuit 6 is stored as the column position.

The connection relationship storage unit 9 includes a connection relationship memory 5 for storing connection relationships between labels, a selection circuit 510, a memory read register 520, and a write register 530.

The selection circuit 510 receives the control signal S-5 from the control section.
11-1 sends signal S-401, control signal S-51
1-2 for signal S-261, control signal S-511
-3 selects and outputs signal S-801.

The connection relation memory 5 uses the output of the selection circuit 510 as an address, and receives the control signal S-501- from the control section.
The output of register 530 is written under control signal S-501-2 and read into register 520 under control signal S-501-2. Here, the connection relationship memory 5 is initially cleared.

Therefore, the labels that are connected are stored in the label counter 4 and the register 530, or in the register 26.
Since it is set to 0 and register 530,
Control signal S-511-1 and control signal S-501-
1 or control signal S-511-2 and control signal S-501-1.

After the entire memory has been accessed, the element processing unit 8 is started.

The element processing unit 8 includes a counter 800 and a comparison circuit 8
The counter 800 is initially cleared and incremented by 1 each time the control signal S-802 is sent from the control section.

The output signal S-801 of the counter 800 is selected by the control signal S-511-3 of the selection circuit 510 and becomes the address of the connection relationship memory 5. Control signal S-
501-2, the connection relationship memory 5 is read out and set in the register 520, and
A comparison circuit 810 detects whether the output signal S-521 is equal to the signal S-801 used as the address, and if they are equal, outputs "1" to the line 811.

The fact that the signal S-811 is "0" means that partial elements of different labels are connected, and the part corresponding to the label value of the output signal S-801 of the counter 800 used as the address of the connection relationship memory 5 The starting point coordinates of the element are no longer required.

Therefore, the output signal S-801 of the counter 800 and the signal S-811 are sent to the control section, and the signal S-811 is sent to the control section.
When the partial element starting point coordinate memory 10 is read by addressing the output signal S-801 when is "1", the obtained coordinate value becomes the starting point of the element.

FIG. 6 shows that in order to trace a line of a binary pattern with a line width of 1 bit according to the present invention, in addition to end points and branch points, element starting points of loop elements included in the pattern are scanned once. This is a diagram showing an example in which detection is possible, and is configured by adding a feature point inclusion relationship processing section 70 and a feature point detection circuit 90 to FIG. 5. Here, the feature point detection circuit 90 is a general circuit that detects whether it matches the mask shown in FIG. 2, and if it matches, outputs the coordinates of the center position. Feature point coordinate memory 7
Set to 00.

FIG. 7 is a detailed diagram excluding the feature point detection circuit 90 of FIG. 6. In the following, the explanation will be made excluding the portion explained in FIG. 5.

The feature point inclusion relationship processing unit 70 includes a feature point coordinate memory 700, a feature point inclusion relationship memory 710, registers 720, 730, 740, and a comparison circuit 75.
0,760,770, AND gate 780,
It consists of an OR gate 790.

Coordinate addresses of feature points detected by scanning the binary pattern memory 1 with the mask shown in FIG. and the counter 220 starts, and the counter 22
The coordinate values of the feature points are set in the register 720 using the output signal S-221 of 0 as an address.

The minutiae inclusion relationship memory 710 is a memory that uses labels as memory addresses and stores whether minutiae are included in the partial elements of each label, and a value of "1" indicates that minutiae are included.
Therefore, memory 710 is first cleared.

The memory 710 is read out to the register 730 using the signal S-232 representing the label value given to the run length data as an address, or
A value of 40 can be written.

The comparison circuit 750 inputs the signal S-611 representing the column address of run-length data and the signal S-721 representing the column address of the feature point, and outputs "1" if they match, and outputs "1" if they do not match. Outputs 0''.

The comparison circuit 760 receives the output signal S-1 of the register 130 in which the value of the run length data is set.
31 and a signal S-72 representing the column address of the feature point.
2 and the value of signal S-722 becomes signal S-1.
If it is greater than or equal to the value of 31, it outputs "1", otherwise it outputs "0".

The comparison circuit 770 receives a signal S-722 representing the column address of the feature point and an output signal S-14 of the register 140 in which the value of the run length data is set.
1 and the value of signal S-141 becomes signal S-7.
If the value is greater than or equal to 22, "1" is output; otherwise, "0" is output.

AND gate 780 is the comparison circuit 750, 76
Since the output of 0,770 is input, "1" is output only when the column coordinate of the feature point matches the column address of the run-length data and the row coordinate is within the row position address of the run-length data.

Register 7 in which the value of memory 710 whose address is the OR gate 790 label value is set
30 and the output of AND gate 780 as inputs, and only when the value of register 730 is "0" and the output of AND gate 780 is "0", "0" is used, that is, the label value used for the address of memory 710. It outputs "0" only when the subelement does not yet include a feature point and the obtained run length data does not include a feature point, and otherwise outputs "1" and sets it in the register 740. Ru.

The value set in register 740 is signal S-2.
32 as the address and stored in the memory 710. Therefore, at the stage when the entire binary pattern memory 1 has been accessed, the feature point inclusion relationship memory 710 stores whether or not feature points are included in the partial elements of each label.

On the other hand, since it can be determined from the signal S-811 of the element processing unit 8 whether partial elements of different labels are connected, the output signal S-801 of the counter 800 and
Output signal S-811 of comparison circuit 810 and signal S
- Register 7 where the value read out from feature point inclusion relationship memory 710 using address 801 is set.
30 output signal S-731 is sent to the control unit, and the signal S-811 is "1" and the signal S-731 is "0".
When the partial element starting point coordinate memory 10 is read using the signal S-801 when , as an address, the starting point coordinates of an element that does not include a feature point, that is, a loop element, are obtained.

As explained above, the present invention provides (1) a device for detecting the starting point of each element of a pattern that does not require an increase in memory in proportion to the number of points in one scanning line; In the case of a binary pattern, it is possible to provide a starting point detection device for loop elements that cannot be detected by a mask.

[Brief explanation of the drawing]

Fig. 1 is a diagram showing an example of a binary pattern including a loop element, Fig. 2 is a diagram showing an example of a mask for detecting end points and branch points, and Fig. 3 is a diagram showing an example of an element detection means using run length data. FIG. 4 is a block diagram showing the relationship between each memory, and is a diagram for explaining the processing in FIG. 3, where a is an example of a pattern set in the binary pattern memory in FIG. c is the change in the contents of the run length memory in Figure 3.
d is the change in the contents of the label memory in Figure 3.5.
e is the change in the content of the connection relationship memory in Figure 3.4.
The changes in the contents of the level counter are shown in correspondence with the columns in FIG. 4a. FIG. 5 is a block diagram of an embodiment for detecting the element starting point of an element included in the pattern of the present invention, and FIG. 6 is a block diagram of an embodiment for detecting the element starting point of a loop element included in the pattern of the present invention. The block diagram in FIG. 7 is a detailed block diagram excluding the feature point detection circuit 90 of FIG. In the figure, 1 is a binary pattern memory, 6 is an address generation circuit, 7 is a partial element connection relationship processing unit,
8 is an element processing section, 9 is a connection relation storage section, 10 is a partial element starting point coordinate memory, 11 is a run length detection section, 70 is a feature point inclusion relation storage section, and 90 is a feature point detection circuit.

Claims (1)

[Claims] 1. A pattern memory that stores a binary pattern of "0" and "1", and a position address A of "1" that changes from "0" to "1" in each column of the pattern memory. run length detection means for storing a position address B of "0" that changes from "1" to "0" after detection of A as a set of run length data A and B;
A connected block of the binary pattern is used as an element, run length data obtained by the run length detection means is used as a partial element, and the partial element is combined by checking the connection relationship with the partial element one row before in the detection order. A partial element connection relation processing means for assigning and storing a label based on the relationship, and data obtained by the run length detection means are received, and run length data that is not connected to run length data one row before is assigned to the partial element connection relation. First run length data C, D of label partial elements given by processing means
a partial element starting point coordinate storage means for storing the starting point coordinates of the partial element where C is the row coordinate and the current column address is the column coordinate; and element starting point processing means for extracting the starting point of a pattern. 2. A pattern memory that stores binary patterns of "0" and "1" with a line width of 1 bit, and a feature check that extracts end points and branch points of the pattern in the pattern memory as feature points and stores their position addresses. and a position address A of "1" that changes from "0" to "1" in each column of the pattern memory and a position address B of "0" that changes from "1" to "0" after detection of A. A run length detection means for storing a set of run length data A and B, a connected block of the binary pattern as an element, data obtained by the run length detection means as a partial element, and a partial element; a partial element connection relationship processing means for examining the connection relationship with the partial element one row before in the detection order and giving and storing a label based on the connection relationship; and a feature point position address obtained by the feature point detection means. partial element feature point inclusion relationship processing means for detecting and storing whether or not the run length data obtained by the run length detection means is included in a subelement; The run-length data that is not connected to the data is the first run-length data C and D of the partial element of the label given by the partial element connection relation processing means, and the starting point of the partial element with C as the row coordinate and the current column address as the column coordinate. A starting point coordinate storage means for a partial element that stores point coordinates, a loop starting point of an element that does not include a feature point from the partial element connection relationship, the partial element minutiae inclusion relationship, and the starting point coordinate of the partial element. 1. An element starting point detection device for a pattern, comprising: element starting point processing means for extracting points.