KR100587540B1 - Apparatus and method for searching for digital ink query - Google Patents

Abstract

The present invention relates to an apparatus and method for retrieving a word corresponding to a query word of a user from a memo input by a user using a digital pen interface.

An apparatus according to the present invention includes a preprocessor for reducing information amount by removing various unnecessary portions from digital ink data for an input query word or memo, a feature extraction unit for extracting a feature vector from the data with reduced information amount, and It consists of a query search unit for searching whether the query is a matching part of the memo in units of segments.

According to the present invention, accuracy and speed can be achieved in a method of searching for desired contents in a pre-written memo or document by inputting a query using a digital pen.

Character recognition, digital ink, spotting table, similarity

Description

Apparatus and method for searching for digital ink query}

1 shows an example of a digital ink memo.

2 is a diagram showing an example of a digital ink query word.

3 is a block diagram showing a configuration of a digital ink retrieval apparatus according to an embodiment of the present invention.

4 shows an example of a memo displayed to a user.

5 is a block diagram showing the structure of a query search unit 50;

6 is a diagram illustrating an example of dividing a query word into segments.

7 shows an example of a spotting table.

8 illustrates an example of a method of determining the priority of a segment according to the amount of information of each segment.

9 is a diagram illustrating an example of comparing similarity with respect to a specific segment of a query and an entire area of a memo;

10A illustrates an example of a 'nearby search' process.

10B is a diagram illustrating an example of an 'expanded neighbor search' process.

FIG. 11 is a tree representation of an example of an 'expanded neighbor search' process. FIG.

12 is a diagram illustrating a sporting method using character segmentation meta information;

(Symbol description of main part of drawing)

10: digitizer 20: preprocessor

30: feature extraction unit 40: memo DB

50: query search unit 60: display unit

100: digital ink retrieval device

The present invention relates to a character input device, and more particularly, to an apparatus and method for searching for a word corresponding to a user's query word in a memo input by a user using a digital pen interface. will be. Here, the digital pen interface is a pen-type device written on a piece of paper using a device that detects a pressure or an electronic signal by touching a screen such as a touch screen and detects a pressure or an electronic signal in an electronic form. It is an interface that implements the traditional way in digital form.

Recently, due to the development of digital technology, the spread of digital devices is progressing rapidly, showing various development trends such as miniaturization and light weight. In particular, keyboard and mouse interfaces, which have been firmly established as interfaces for digital devices in recent decades, have been pointed out in terms of portability as digital devices have been miniaturized. The need for an alternative interface to solve this problem has been pointed out for decades, and to develop alternative interfaces using voice, pen, gesture, video, etc. Research has been ongoing. Among them, pen and voice interface, which has been used as a means of communication in human society for thousands of years, is attracting attention because of its vastness of naturalness and expressive power.

The digital pen interface is an attempt to apply a habit of communication to a digital device that writes letters, degrees, symbols, etc. using a pen on paper. As a method for digitizing the pen interface, character recognition technology has been steadily researched. Character recognition technology uses pattern recognition technology to recognize character information (hereinafter referred to as 'ink') inputted by digital pen and convert it into ASCII code form that expresses characters in computer. Means technology.

However, the letter recognition technology is not easily distributed to the users compared to the results of the research, and there are two main reasons for the barrier of the diffusion. First, the character recognition speed is slow. In order for the user to naturally take notes, they must be recognized and processed without any time delay during the continuous writing process, but in fact, a 0.5 second time delay occurs, causing the user to be psychologically frustrated to proceed continuously. Cause.

Second, it can be pointed out as a barrier due to character recognition error. The current character recognition technology recognizes characters with about 90% accuracy in real life situations, but it is also a performance in an environment where various interface aids are provided to facilitate the distinction between characters. Can be. If an error occurs in the process of continuously recognizing the user's handwriting, the user takes an action for correcting the error, which also acts as an obstacle to continuity.

As an alternative to overcome this weakness of the character recognition technology in the field of pen interface, the digital ink, i.e., the trajectory of the digital pen, is used, and the character recognition process (which of the ASCII codes corresponds to Techniques that do not go through the process of making decisions are being proposed. As shown in FIG. 1, a method of digitizing and storing a detected pen trace as it is detected and displaying the contents as it is is provided so that a user can obtain information recorded by the user. Since this method does not go through the character recognition process, it is possible to overcome the disadvantages of the character recognition technology by not disturbing the natural movement of the user's hand.

However, since the interface is not stored in the form of computer-recognized coded characters, when the user wants to search for the desired information in the future, the user must directly check all the recorded information. . In order to overcome this disadvantage, a retrieval technique for a medium recorded with digital ink has to be developed. In this regard, in a situation where a large number of memos (hereinafter referred to as 'notes') recorded in digital ink exist as shown in FIG. 1, a search query form (hereinafter referred to as a "query") in the form of digital ink is input as shown in FIG. 2. In this case, there is a technology (hereinafter, referred to as a 'digital ink search technology') of displaying a memo including a portion of the query word 'wedding' as a search result.

The conventional method for digital ink retrieval is based on the premise that the unit to be searched is divided into word units, or that there is no problem in dividing into words by writing a sufficiently wide interval between words.

If both query and memo are divided into word units, it can be processed simply by comparing similarity between query and memo using methods such as Elastic Matching proposed in various literatures. In such a situation, since the object to be compared and searched is clear, there is no problem in dividing into words, and speed is not a big problem. The Elastic Matching method is well described in C.C.Tappert's article "Cursive Script Recognition by Elastic Matching (IBM J. Research Development, V.26, No.6, pp.765-771, 1982)." This method compares two confirmed subjects, and as a result shows the numerical similarity between the two subjects.

However, in reality, many of the digital devices have small input screens, and in such devices, there are many cases in which the user inputs without spaces between words because there is no space between letters or words due to space limitation or not wide enough for easy division. . In addition, even if there is enough space for input, strict spacing may not be used depending on the characteristics of the user. In such a situation where it is difficult to divide the search object, it is difficult to solve even which part of the memo should be compared with the memo, and thus the fundamental problem is encountered.

 Accordingly, the present invention has been made in view of the above-described problems, and an object of the present invention is to provide a method for a user to generate a plurality of memos using a digital pen, and to implement a search function for a query word input by the user thereafter. It is done.

Another object of the present invention is to provide a method for spotting using only a specific part of a query in order to implement the above-described search function.

Another object of the present invention is to provide a method of using additional meta information in order to implement the above-described search function.

In order to achieve the above object, the digital ink retrieval apparatus according to the present invention includes a pre-processing unit for reducing the amount of information by removing various unnecessary portions from the digital ink data for the input query word or memo; A feature extractor for extracting a feature vector from the data whose information amount is reduced; And a query search unit that searches whether the query is a matched part of the memo in segment units.

The digital ink retrieval apparatus may further include a digitizer which receives a stroke of a user and recognizes the stroke as digital ink data and transmits the digital ink data to a preprocessor.

The digital ink retrieval apparatus may display a memo including the matched portion to the user by emphasizing the matched portion as a result of the search, and if the matched portion does not exist in the entire memo, the display unit notifies the user of the result as a message. It is preferable to further include.

The digital ink retrieval apparatus further includes a memo DB for storing the memo data in the form of a feature vector extracted from the feature extraction unit when the input stroke is a memo, and providing the stored memo to the query retrieval unit when the query is retrieved. It is desirable to.

The query search unit may include: a segment dividing unit dividing a character represented by the feature vector into segments by using temporally input order information or spatial separation information; A search rank determiner which determines a rank to search for the divided segments and provides the same to a spotting unit; A spotting unit that searches a cell whose similarity exceeds a predetermined threshold (a) by comparing a segment of a query word having the highest ranking among the determined rankings using a spotting table with a segment of a memo; And a periphery search unit for searching the periphery of the cell from the searched cell and checking whether there is a portion corresponding to the corresponding memo for the entire query.

Preferably, the search rank is determined based on the amount of information of each segment.

The spotting table is composed of cells having multiple levels of contrast divided into rows and columns. The cell where the i th column and the j th row meet is the i th segment of the query and the j th segment of the searched memo. It is desirable to record the result of comparing the similarity.

It is preferable to use the Elastic Matching method to obtain the similarity.

Searching the periphery of the cell is performed in the diagonal direction of the cell, but preferably until the upper and lower ends of the spotting table are reached.

The search of the periphery of the cell is performed in the diagonal direction of the cell, but the candidate group of the next node to be selected is selected through the horizontal expansion and the vertical expansion, and according to the best first search method, the most similarity among the search results so far is It is desirable to search until you reach the top and bottom of the spotting table, extending continuously from the high part.

The coincidence portion may determine a cumulative similarity of the search result until reaching the upper end and the lower end, and means the corresponding part in the memo when the cumulative similarity exceeds a predetermined threshold (b).

로 표시되는데,

는 현재 노드에서 사용하는 질의어 세그먼트의 길이를,

는 다음 노드에서 확장된 질의어 세그먼트의 길이를,

는 질의어의 i번째 세그먼트와 검색 대상 메모의

번째 세그먼트의 유사도를 의미하는 것이 바람직하다.In the case of selecting a cell in the diagonal direction as the next node without expansion among the candidate groups, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the i-th segment of the query and

It is preferable to mean the similarity of the first segment.

로 표시되는데,

는 현재 노드에서 사용하는 질 의어 세그먼트의 길이를,

는 다음 노드에서 확장된 질의어 세그먼트의 길이를,

는 다다음 노드에서 확장된 질의어 세그먼트의 길이를,

는 질의어의 i+1번째 세그먼트와 i+2번째 세그먼트를 합한 것과 검색 대상 메모의

번째 세그먼트의 유사도를 의미하는 것이 바람직하다.In the case of vertical expansion among the candidate groups, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the length of the expanded query segment at

Is the sum of the i + 1th and i + 2th segments of the query, and

It is preferable to mean the similarity of the first segment.

로 표시되는데,

는 현재 노드에서 사용하는 질의어 세그먼트의 길이를,

는 다음 노드에서 확장된 질의어 세그먼트의 길이를,

는 질의어의 i+1번째 세그먼트와, 검색 대상 메모의

번째 세그먼트와

번째 세그먼트를 합한 것의 유사도를 의미하는 것을 특징으로 하는 것이 바람직하다.In the case of vertical expansion among the candidate groups, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the i + 1th segment of the query, and

Segment and

It is preferable to mean that the similarity of the sum of the second segment.

The determining of the search rank may be performed by dividing the query word and the memo by character units, and determining the search rank only for segments corresponding to the beginning or the end of a character among the segments of the query word.

Comparing the segment of the query word with the segment of the memo, the segment corresponding to the beginning or end of the character in the search target memo, depending on whether the segment determined as the highest priority among the search rankings is the beginning or the end It is preferable to compare only with these.

In order to achieve the above object, the digital ink retrieval method according to the present invention comprises the steps of reducing the amount of information by removing various unnecessary portions from the digital ink data for the input memo; Extracting a feature vector from the memo data whose amount of information has been reduced and storing it in a memo DB; Reducing the amount of information by removing various unnecessary portions from the digital ink data for the input query word; Extracting a feature vector from the query data having the reduced information amount; And searching whether the query word has a matching part in the memo in units of segments.

The searching in the segment unit may include: dividing a character represented by the feature vector into segments by using temporally input order information or spatial separation information; Determining a rank to search for the divided segments; Searching a cell whose similarity exceeds a predetermined threshold (a) by comparing a segment of a query word having the highest rank among the determined rankings using a spotting table with a segment of a memo; And searching the periphery of the cell from the searched cell and checking whether there is a part corresponding to the corresponding memo for the entire query word.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Advantages and features of the present invention and methods for achieving them will be apparent with reference to the embodiments described below in detail with the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be implemented in various different forms, and only the embodiments make the disclosure of the present invention complete, and the general knowledge in the technical field to which the present invention belongs. It is provided to fully convey the scope of the invention to those skilled in the art, and the present invention is defined only by the scope of the claims. Like reference numerals refer to like elements throughout.

The digital ink retrieval apparatus according to the embodiment of the present invention is configured as shown in FIG. The digital ink retrieval system 100 includes a digitizer 10, a segment divider 20, a preprocessor 30, a feature extractor 40, a memo DB 40, a query search unit 50, and a display unit ( 60).

The digitizer 10 receives the user's stroke and recognizes it as pixel-specific binary data, that is, digital ink data, and transmits it to the preprocessor. The resolution of the digitizer 10 may be input at, for example, about 150 points per inch, and may be transmitted to the processor at a speed of 50 points per second.

The preprocessor 20 reduces the amount of information by removing various unnecessary portions of the input digital ink data. The unnecessary portion is generated due to incompleteness of a user's stroke input, a variety of character sizes, a variety of writing speeds, and the like. Such pre-processing may include processes such as de-hooking, resampling, and the like. De-hooking is a process of removing hooks that appear at the beginning and end of a stroke (a unit of writing at once without removing the pen) during the pen input process. Resampling is a process to reduce the amount of information while minimizing the distortion of the information. It is a process of deleting points except for the point where the change is large.

Feature extraction 30 extracts feature vectors from the filtered data through preprocessing. The feature vector may include, as information, an angle, a length of a line to which the dot is connected, and various other information may be used as the feature information. Many conventional methods exist for this feature extraction process, and any one of them can be used in the present invention. See, eg, BKShin, JYHa, SCOh, Kim JH, "Network-based approach to online cursive script recognition" (IEEE Trans. On Systems, Man and Cybernetics, Part B, V.29, Issue 2 , 1999) may use the method of feature extraction.

The stroke input by the user may be a simple 'memo data' or may be a 'query' to find a matching portion of the memo data. If the input stroke is simple memo data, the memo DB 40 stores the memo data in the form of a feature vector extracted from the feature extractor 30.

On the other hand, if the input stroke is a query, it is input to the query search unit 50 without passing through the memo DB 40.

The query retrieval unit 50 is a core part of the present invention. The query retrieval unit 50 searches whether the query unit has a matching part in the memo data stored in the memo DB using a predetermined matching algorithm and transmits the search result to the display unit. .

The display unit 60 displays the memo in which the matching part exists as a result of the query search to the user by highlighting the matching part, and notifies the user as a message if there is no matching part in the whole memo. 4 illustrates an example of a memo displayed to the user.

5 is a block diagram showing the configuration of the query search unit 50. The query search unit 50 may include a segment divider 51, a search rank determiner 52, a spotting unit 53, and a peripheral search unit 54.

The segment dividing unit 51 divides the characters represented by the feature vectors into division units, that is, segments, using temporal information (temporal input order information) or spatial information (spatial information). do. A segment can be defined as a separate part of a character input by a user without being connected to another part. Therefore, in the case of Korean, it can be a phoneme such as one consonant, a vowel, etc., and in the case of English, it can be one alphabetic character. However, depending on the user's handwriting method, two phonemes may be recognized as one segment, and one phoneme may be recognized as two segments. Thus, segmentation indicates that the user's input actually represents the same character. Even if the user's writing method can be variable.

It should be noted that what is described as 'separately separated' includes not only spatially separated but also temporally separated. For example, in the example of FIG. 2, 'ㄹ' of 'grain' is spatially connected to 'o' of 'soul', but is not connected in time. When the user inputs a memo or query through the digitizer, the digitizer knows not only the final form but also the order of the strokes. 'Is not counted as one segment.

There may be several criteria for determining segmentation by segment. For example, it may be recognized that one segment is completed and the next segment starts based on the moment when the contact of the pen device falls off the surface of the digitizer. In the case of the English language, it may be divided based on the local maximum and minimum points, or may be divided based on the ligature point through connection stroke analysis. In addition, there are various conventional methods for recognizing segments, and in the present invention, one method may be selected and used.

An example of dividing the query word of FIG. 2 by segment is shown in FIG. 6. Each segment is arranged according to the temporal order inputted by the user into the digitizer, and the i value indicates the order of arrangement. Note that this is only an input temporal order and not a search order.

Meanwhile, in the present invention, the segment is preferably defined as above, but one stroke (stroke) may be defined as the segment without being limited thereto. In general, if the stroke is selected as a segment, the division of characters is too large and the search performance is often decreased. However, in case of using a writing method that does not have much space (for example, English handwriting), it is rather a unit of stroke. It would be more advantageous to divide by.

The search ranking unit 52 determines a ranking to search for the segments divided by the segment dividing unit 51. In order to produce a meaningful result of the spotting process performed by the spotting unit 53, the following two basic conditions must be satisfied. First, complexity must be reduced sufficiently. Second, the results of spotting must be meaningful enough. In order to satisfy such a condition, for each segment divided by the segment dividing unit 51, segments that can satisfy the above two conditions are prioritized, and their application order is determined. In order to satisfy the first condition, the divided part must be a unit sufficiently small compared to the entire query word. In order to satisfy the second condition, the divided part should not be a simple pattern, and a pattern which does not occur frequently in general is better.

Referring to the spotting table of FIG. 7 (more detailed description of FIG. 7 will be described later), when spotting with 1) portions, a total of 3 spots are spotted, while spotting with 2) portions has a total of 8 spots. It can be seen that spotting is in progress. In other words, when spotting 2), the spotting (False Alarm) frequently occurs, whereas when spotting 1), the number of spotting is less. However, if spotting proceeds to 1), the probability of false rejection increases, so the query must be divided and the spotting order determined in such a way that the above two conditions can be compromised.

An example of a method of determining the priority of a segment according to the information amount of each segment will be described with reference to FIG. 8. As a method of determining the amount of information of each segment, the number of points appearing after the preprocessing in the preprocessor 20 is used. That is, if the number of points constituting the segment is large, it is determined that the information amount of the segment is large, and the priority of the search is given to the segment having a large amount of information.

In FIG. 8, four points of each part of the query word have a total priority of four. Random selection can be used to determine the order to use for spotting.

The spotting unit 53 searches a cell exceeding a threshold by comparing a query segment having the highest rank among the determined rankings with a memo segment using the spotting table.

Spotting is a method of avoiding the complexity of comparing the whole, and is a method of scanning a search object by segment of a query to be searched.

One of the biggest problems in digital ink retrieval is that it is not easy to divide the memo to be searched into specific units for retrieval. For example, to search whether or not the query 'wedding' of FIG. 2 exists in the memo as shown in FIG. 1, an ordered combination of all possible strokes in the memo should be extracted to compare the similarity with the query. In other words, similarity should be compared to 'friend wedding', or similar to 'wedding cod', 'paradise', 'old marriage', or even 'part' which is part of the stroke. Occurs. This is due to the fact that it is difficult to pinpoint the boundaries between characters.

In this way, the complexity of the search is so high that it cannot be used in practice. In any way, it is possible to process whether there is actually a part of the query in the memo, and if so, only as few similarity comparisons as possible. This is necessary.

In the present invention, as a method for realizing a fast search, instead of searching for all possible candidates, only a specific part of a search word is extracted and searched, and a more detailed search is only performed when a search result is obtained with a high similarity to the corresponding part. A method of realizing speeding up in a progressive manner will be described.

In the present invention, as shown in Figure 7, by searching only a portion of the query through the method of spotting (spotting) by greatly reducing the unit of similarity search significantly reducing the search time and at the same time compare the similarity of the actual query Use a method of reducing the number of times.

For example, as shown in FIG. 9, the similarity is compared with respect to a specific segment of a query (eg, a supporting 'o' portion) and the entire area of the memo. As a result of the similarity comparison, the parts similar to the support 'ㅇ' show that the support parts of 'cheon', 'up', 'jin' and 'row' can be detected as similar. The similarity with the entire area of the query can be compared by searching for the remaining parts from the spotted spots.

An example of a spotting table for clearly performing the spotting process is illustrated in FIG. 7. The spotting table consists of squares with multiple levels of contrast, separated by rows and columns. Columns mean that the query is divided into segments and then divided into units. Rows mean that the memo to be searched is divided into units of search and expanded by each unit. That is, the cell where the i th column and the j th row meet is a result of comparing the similarity between the i th segment of the query and the j th segment of the search target memo.

Contrast of each square means the result of comparing similarity of each cell. The darker the darker the cell, the more similar the two segments are to be compared. In particular, the cells marked in red exceed the spotting threshold, which means that the segment of the query and the segment of the note match.

Looking at the spotting process in more detail, it is determined whether there is a matching segment in the memo while proceeding in the horizontal direction (the direction of increasing j) with respect to the query segment having the highest priority according to the search order of the query search unit 50 among the query segment. Find. If there is no matched segment, then a query segment having a rank after the first search order is searched for a matched segment in the same manner.

Determining whether to match, compares the similarity between the specific segment of the query currently used for spotting and the specific segment of the memo, outputs it in a normalized form with [Min, Max] value, and compares the calculated value with the threshold If the threshold value is exceeded, it is determined as a match, and the matched cell is defined as a 'spotted cell'.

If the calculated similarity value is smaller than the threshold, the next segment of the memo is selected and the same process is repeated. The similarity comparison method may use various methods that can express the comparison result as a normalized numerical value using the aforementioned Elastic Matching method. The similarity comparison result calculated during the spotting process is calculated only when necessary by preparing and storing the similarity table, and do not duplicate the calculation.

The periphery searcher 54 searches the periphery of the cell from the searched (ported) cell and checks whether there is a part of the query that matches the corresponding memo. If there is a segment of the memo that matches the segment of the current query word through the spotting process in the spotting unit 53, the similarity in the next cell is moved while moving from the corresponding cell to the top and bottom of the spotting table diagonally. Calculate and write (mark in color) to the cell. This process is repeated until all cells in the diagonal direction have been processed.

Here, the diagonal direction means the upper left or the upper right direction, and moving in the upper left direction moves to a cell having the coordinate (i-1, j-1) when the current cell coordinate is (i, j), which is a query word. This compares the previous segment of to the previous segment of the note. And, moving in the lower-right direction is to move to a cell having (i + 1, j + 1) coordinates when the current cell coordinate is (i, j), and compares a later segment of the query with a later segment of the memo. . This process is called 'nearby'.

For example, as shown in FIG. 10A, the similarity is calculated and recorded in all cells in the direction while moving in the upper left direction based on the matched cell A. FIG. After that, while moving from the cell A to the lower right direction, the similarity in all the cells in the direction is calculated and recorded.

As described above, the process of comparing similarities in the diagonal direction is based on the premise that the query segment and the memo segment correspond to each other one by one, but according to a writing method, a plurality of phonemes may be included in one segment, and one phoneme may be It may be recognized as a plurality of segments.

In order to solve this problem, it is preferable to proceed with the search while extending from the spotted point using similarity information matched for each part unit and length information of each part.

10B illustrates the manner of performing an extended search from the spotted cell. Here, the part drawn with green border marks the correct answer corresponding to the segment of the actual query and the segment of the memo. Pointing from the spotted cell B in the direction of arrow (a), that is, no expansion indicates comparing one query segment and one memo segment. The expansion in the direction of arrow (b), ie, the horizontal expansion, indicates the comparison between the sum of one query segment and two memo segments. In addition, expanding in the direction of arrow (c), that is, vertical expansion indicates comparing two query term segments with one memo segment.

Horizontal expansion is a method in which two phonemes are recognized as one segment in a query and a phoneme is recognized as one segment in a memo. The vertical extension is a method in which one phoneme is recognized as one segment in a query and two phonemes are recognized as one segment in a memo.

To overcome the problem of merging these phonemes by handwriting, we simultaneously test the possibility that several phonemes have been merged in one step expansion, and use the Best First Search algorithm to compare the results of the expanded partial results to the present. Use the method of extending continuously from the most similar part among them. This process is called extended search.

If the two-stage expansion (horizontal direction 2, longitudinal direction 2 expansion) is used as shown in FIG. 10B, there are three node candidate groups, and the one with the highest similarity may be selected. If using a three-stage extension, there may be five node candidate groups.

The algorithm shown in FIG. 10B may be represented in a tree form as shown in FIG. 11. The search process is performed until the boundary point is reached at the upper left and the lower right on the similarity table. In FIG. 11, a process of searching from one spotted cell in the right-bottom direction is taken as an example. Here, one red square corresponds to one time of Elastic Matching, which is defined as a node. One node may consist of one cell or one or more cells.

라고 할 때, (1)의 형태처럼 질의어의 한 세그먼트를 확장하는 경우, 아래의 식 1과 같이 누적 유사도를 각 세 그먼트의 길이에 비례하여 정규화된 형태로 계산할 수 있다.An embodiment of the calculation method of similarity in performing such an extended neighbor search is as follows. Similarity at node C of FIG.

In this case, when one segment of the query is extended as in the form of (1), the cumulative similarity may be calculated in a normalized form in proportion to the length of each segment as shown in Equation 1 below.

[식 1]

[Equation 1]

,

는 각각 현재 노드에서 사용하는 질의어 세그먼트의 길이, 다음 노드에서 확장된 질의어 세그먼트의 길이를 의미하며,

는 질의어의 i번째 세그먼트와 검색 대상 메모의

번째 세그먼트의 유사도를 의미하고,

는 질의어의 i+1번째 세그먼트와 검색 대상 메모의

번째 세그먼트의 유사도를 의미한다.here

,

Means the length of the query segment used in the current node and the length of the query segment extended in the next node.

Is the i-th segment of the query and

The similarity of the first segment,

Is the i + 1th segment of the query and

The similarity of the first segment.

는 다다음 노드에서 확장된 질의어 세그먼트의 길이를,

는 질의어의 i+1번째 세그먼트와 i+2번째 세그먼트를 합한 것과 검색 대상 메모의

번째 세그먼트의 유사도를 의미한다.Likewise, in the case of extending using two segments of the query as in the form of (2), the cumulative similarity is calculated as in the following [Formula 2]. here,

Is the length of the expanded query segment at

Is the sum of the i + 1th and i + 2th segments of the query, and

The similarity of the first segment.

[식 2]

[Equation 2]

는 질의어의 i+1번째 세그먼트와, 검색 대상 메모의

번째 세그먼트와

번째 세그먼트를 합한 것의 유사도를 의미한다.Likewise, in the case of extending using two segments of the query as in the form of (3), the cumulative similarity is calculated as in the following [Formula 3]. here,

Is the i + 1th segment of the query, and

Segment and

The similarity between the sum of the first segment.

[식 3]

[Equation 3]

As such, the results of the expandable part are continuously extended from the most similar part of the search results to date using the Best First Search algorithm. For example, if (1) direction search, (2) direction search, and (3) direction search are performed in FIG. 11, and as a result, the cumulative similarity of (1) direction search is the highest among the search results to date. In the result of direction (1), we proceed one step further search. (3) If the cumulative similarity is greater than or equal to a predetermined threshold, such as in a direction search, the search path is truncated without further searching.

In the above extended search process, if the extended search is performed until the end of the search direction (top and bottom) is reached and the cumulative similarity is found to be greater than or equal to the threshold value, the search is stopped and the corresponding part of the path in the memo is optimally matched. Select by part.

If you pass the above spotting process and search for neighbors, but there are no paths that exceed the threshold value, it may be determined that there is no similar part to the query word in the memo, and the path having the highest value among the cumulative similarities for each calculated path. May be presented as a candidate.

Applying the above-mentioned spotting method, a sequential search is performed on a part of the query word used for spotting and all parts of the search target memo. However, if additional information that can be derived from the actual handwriting information (hereinafter referred to as meta information) can be obtained, a faster speed can be obtained by selectively comparing only the parts with matching characteristics without comparing similarities with all parts of the searched memo. have.

An example of using character segmentation information as meta information is an example. It is not possible to divide the input digital ink by character unit 100% accurately, but it is possible to obtain the result of character unit division with high accuracy by utilizing various information. Although this information is not accurate and cannot be used in the next step with confidence, the present invention can be used to avoid meaningless comparison attempts in the spotting process.

12 illustrates a spotting method using character segmentation meta information. As described above, each column and row of FIG. 12 denotes similarity between respective parts of the query word and the memo. Given character segmentation meta-information, it is possible to mark a boundary point between each character like a blue line.

In this situation in which the meta-partitioned meta information is given, an operation process (segment division process) in the segment division unit 51, an operation process (search rank determination process) in the search ranking unit 52, and a spotting unit ( 53, the operation process (spotting process) is different.

First, in the segmentation process, only the segments corresponding to the beginning or end of a given character in meta information are used for spotting. For example, in FIG. 12, a query word is divided into two characters, and a total of four start segments and end segments exist. In this case, therefore, the search rank is determined for the four segments based on the amount of information.

Next, a selective search is performed using the character segmentation information given as meta information. For example, if the segment currently used for spotting is a segment corresponding to the beginning of the character of the query, the search target memo also selectively compares only the segment corresponding to the beginning of the character. Similarly, if the segment corresponds to the end of the character, the memo compares only the segment corresponding to the end of the character. This comparison process is shown by the arrow in FIG.

In addition to the above-described embodiment of using meta information, the above-described embodiment is applied to compare only the segments of the portion of the character near the corresponding position by using the topology information occupied by the feature segment in the character after segmenting the character. The method may also be used. In addition, in the case of English, a method of dividing by a word unit and using meta information may be used.

When applying this method, there is a possibility of slight loss in search performance. However, when applied to handwriting patterns of general users, the loss is small but the effect of speed improvement is very large.

Although embodiments of the present invention have been described above with reference to the accompanying drawings, those skilled in the art to which the present invention pertains may implement the present invention in other specific forms without changing the technical spirit or essential features thereof. I can understand that. Therefore, it should be understood that the embodiments described above are exemplary in all respects and not restrictive.

According to the present invention, accuracy and speed can be achieved in a method of searching for desired contents in a pre-written memo or document by inputting a query using a digital pen.

In addition, according to the present invention, the user can be input quickly without an input delay occurring in the character recognition process can improve the intimacy of the product.

Claims (24)

A pre-processing unit which removes various unnecessary portions from the digital ink data for the input query word or memo to reduce the amount of information; A feature extractor for extracting a feature vector from the data whose information amount is reduced; A segment dividing unit for dividing a character represented by the feature vector into segments by using temporally input order information or spatial separation information; A search rank determination unit to determine a rank to search for the divided segments; A spotting unit which searches for a cell whose similarity exceeds a predetermined threshold (a) by comparing a segment of the query word having the highest ranking among the determined search rankings with a segment of a memo; And And a peripheral search unit which searches the periphery of the cell from the searched cell and checks whether there is a portion corresponding to the corresponding memo for the entire query word. The method of claim 1, And a digitizer which receives a stroke of a user and recognizes the stroke as the digital ink data and transmits the same to the preprocessor. The method of claim 1, The digital ink query further includes a display unit that highlights the matched result as a result of the search and displays the memo including the matched part to the user, and notifies the user of the result as a message if there is no matched part among all the memos. Search device. The method of claim 2, And storing the memo in the form of a feature vector extracted by the feature extracting unit when the input stroke is a memo, and providing the memo when the query is searched. delete The digital ink query retrieval apparatus according to claim 1, wherein the search rank is determined based on the amount of information of each segment. The spotting table of claim 1, wherein the spotting unit uses a spotting table to search for a cell exceeding the threshold (a). It consists of cells with multiple levels of contrast divided into rows and columns. The cells where the i th column and the j th row are compared compare the similarity between the i segment of the query and the j segment of the searched memo. And a result is recorded. The method of claim 1, wherein the similarity is A digital ink quality retrieval apparatus, characterized by being obtained by an Elastic Matching method. The method of claim 1, wherein the peripheral search unit Searching in the diagonal direction of the cell, the digital ink query search device, characterized in that the search until reaching the top and bottom of the spotting table. The method of claim 1, wherein the peripheral search unit The cell is searched in the diagonal direction, and the candidate group of the next node to be selected is selected through horizontal expansion and vertical expansion, and continuously expands from the most similar parts of the search results to date according to the Best First Search method. Searching apparatus for digital ink quality, characterized in that the search until reaching the top and bottom of the spotting table. 11. The method of claim 10, wherein the matching portion And a corresponding portion of the memo when the cumulative similarity of the search result until the upper and lower ends reach a predetermined threshold (b). 12. The method of claim 11, wherein when selecting a cell in the diagonal direction without expansion of the candidate group as the next node, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the i-th segment of the query and

The similarity of the first segment,

Is the i + 1th segment of the query and

And a similarity of the first segment. The method of claim 11, wherein when the longitudinal expansion of the candidate group, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the length of the expanded query segment at

Is the i-th segment of the query and

The similarity of the first segment,

Is the sum of the i + 1th and i + 2th segments of the query, and

And a similarity of the first segment. The method of claim 11, wherein when the longitudinal expansion of the candidate group, the cumulative similarity is

It is displayed as

Is the length of the query segment used by the current node,

Is the length of the query segment expanded at

Is the i-th segment of the query and

The similarity of the first segment,

Is the i + 1th segment of the query, and

Segment and

And a similarity of the sum of the first segment. The method of claim 1, wherein the search rank determining unit And dividing the query word and the memo into units of characters and determining a search rank only for segments corresponding to a start part or an end part of a character among the segments of the query word. The apparatus of claim 15, wherein the search rank determining unit The digital ink query, wherein the segment determined as the highest priority among the search rankings is compared with only the segments corresponding to the beginning or the end of the character in the searched memo according to whether the determined segment is the beginning or the end. Search device. Reducing the amount of information by removing various unnecessary portions from the digital ink data for the input memo; Extracting a feature vector from the memo data whose amount of information has been reduced and storing it in a memo DB; Reducing the amount of information by removing various unnecessary portions from the digital ink data for the input query word; Extracting a feature vector from the query data having the reduced information amount; And searching, by segment, whether there is a matching part of the memo in the memo. The method of claim 17, wherein the searching in segments Dividing a character represented by the feature vector into segments using temporally input order information or spatial separation information; Determining a rank to search for the divided segments; Searching a cell whose similarity exceeds a predetermined threshold (a) by comparing a segment of a query word having the highest rank among the determined rankings using a spotting table with a segment of a memo; And And searching the periphery of the cell from the searched cell to check whether there is a portion corresponding to the corresponding memo for the entire query word. 19. The method of claim 18, wherein the search rank is determined based on the amount of information in each segment. 19. The method of claim 18, wherein the spotting table It consists of cells with multiple levels of contrast divided into rows and columns. The cell where the i th column and the j th row compares the similarity between the i segment of the query and the j segment of the searched memo. And the results are recorded. 19. The method of claim 18, wherein searching the perimeter of the cell is Searching in the diagonal direction of the cell, and searching until reaching the top and bottom of the spotting table. 19. The method of claim 18, wherein searching the perimeter of the cell is The cell is searched in the diagonal direction, and the candidate group of the next node to be selected is selected through horizontal expansion and vertical expansion, and continuously expands from the most similar parts of the search results to date according to the Best First Search method. A method of searching for digital ink quality, characterized in that the search is performed until it reaches the top and bottom of the spotting table. The method of claim 22, wherein the matching portion is And a corresponding part of the memo when the cumulative similarity of the search result until the upper and lower ends are reached exceeds a predetermined threshold (b). A recording medium on which a method according to any one of claims 17 to 23 is recorded by a computer readable program.

Images