KR20060012071A - Common Information Mining Technique for Similar Video Data - Google Patents

Abstract

The present invention relates to a method for extracting knowledge information from a similar video. More particularly, the present invention relates to a method of extracting knowledge information from video data, compressing and refining a video signal, analyzing clustering features using clustering, and then searching a sequential pattern. A data mining system for similar video extracting knowledge information.

To this end, the present invention, in the system for extracting the knowledge information from the video, decomposing the video signal output from the video to represent various video features, after the step of extracting the main frame to compress the resulting data, Refining the data by removing noise or short-term occurrences from the main frame extracted in the above step; Searching the cluster by clustering the data passing through the step; Merging a plurality of clusters represented in the above into logical blocks having the same characteristics, reducing clustering targets by applying separate weights to static and dynamic regions, making extracted knowledge into clustering profiles, and clustering profiles And video day It consists of a sequential pattern mining step of retrieving the sequential pattern from the data.

Video, data mining, clustering, sequential pattern mining, profile, cluster, normal behavior, abnormal behavior, surveillance                                    

Description

Common information mining technique for similar video data {Knowledge Discovery Methods of Similar Video Data}

1 is a block diagram representing the overall system.

2 is a block diagram showing an example of application of the monitoring environment using the present invention.

3 is an example diagram representing merging of pixels in a frame.

4 is an example diagram representing a region of interest setting.

5 is a block diagram representing a process of setting a region of interest.

6 is a block diagram representing a process of applying a minimum repeatability.

7 is a block diagram representing a key frame extraction process.

8 is an example diagram representing an inference block.

9 is an exemplary diagram representing a key frame extraction process.

10 is a block diagram representing an inferred block generation process.

11 is a block diagram representing a static / dynamic block search process.

12 is a block diagram representing a sequential log generation process.

13 is a block diagram representing a sequential pattern mining process.

 <Description of the symbols for the main parts of the drawings>

1: video database 2: feature information extraction

3: characteristic information log 4: ROI setting block

5: minimum repeat processing block 6: key frame extraction block

7: preprocessing characteristic information log 8: clustering block

9: Profile 10: inference block generation block

11: Static / Dynamic Weighted Block 12: Clustering Profile

13: Preprocessing + Clustering + Post Processing Block 14: Decision Block

15a: Object A pixel a

15b: Object A pixel b

15c: object A pixel c

15d: Object A pixel d

16: Base Block 17: Object A

18: Object B19a: Relevant Variable Initialization Block A

19b: Relevant variable initialization block B19c: Relevant variable initialization block C

19d: Relevant variable initialization block D19e: Relevant variable initialization block E

20: Loading the region of interest map 21: Transaction termination confirmation block

22: Final frame check block 23: Final base block check block

24: check whether the region of interest is included block 25: block removing characteristic information

27: characteristic information change determination block 28: characteristic information count determination block

29: characteristic information removal block 30: characteristic information maintenance block

31: group change amount accumulation block 32: group change amount comparison block

33: New group definition block 34: Scene variation comparison block

35: New Scene Definition Block 36a: Base Block Before Merging

36b: Merged Base Block (Inferred Block) 37: Example Using Key Frame Extraction

38: reference base block check block 39: characteristic information difference calculation block

40: change base block check block 41: minimum difference search block

42: threshold check block 43: base block merge block

44: profile loading block 45: block end confirmation block

46: Cluster Count Comparison Block 47: Dynamic Weighting Block

48: static weighting block 49: initialization block

50: characteristic information and cluster comparison block 51: cluster output block

52: Transaction list termination confirmation block 53: Cluster termination confirmation block

54: Cluster List Update Block 55: Cluster List Database

56: minimum support block 57: frame effective cluster extraction block

58: frame valid cluster combination generation block 59: ID conversion block

60: Transaction Effective Cluster Combination Generation Block

61: ID Restore Block 62: Sequential Pattern File

63: sequential log generation block 64: sequential log

65: sequential pattern generation block 66: sequential pattern profile

67: cluster comparison block 68: cluster backup block

The present invention relates to a method of extracting knowledge information from a video, and more particularly, to a process of decompressing and compressing a video signal from collected videos, compressing and purifying them, and extracting knowledge information using clustering and sequential pattern mining. The present invention relates to a mining technique for similar video data including a.

Existing researches on video have a morphological perspective that extracts morphological characteristic information such as color and texture according to the method of interpretation of information extracted from video data, and specifics related to the motion and meaning of objects separated from the background appearing in the video. It is divided into semantic views that extract information. Researches using video features extracted in this way include the field of indexing or categorization into similar categories to provide effective and accurate video retrieval from video databases. Various clustering techniques, such as K-means or Forgy's, have been proposed to find clusters with similar characteristics for data distributed in space and to determine the characteristics and structures inherent in the data. Sequential pattern mining is one of the data mining techniques that finds a common pattern that is sequential from data with temporal distribution. A representative study is Apriori.

However, the existing researches for video interpretation have focused only on a limited field of statistical methods due to the large amount of data in video and the lack of effective mining methods based on its features. In addition, the existing researches for interpreting the semantic elements represented in the video have been used limitedly because it is impossible to clearly understand the object, extract the features and semantic interpretation based on them. In particular, in the case of targeting similar videos, it may be easier to extract feature information that is repeatedly repeated in each video, but research on this has not been actively conducted.

In order to solve the above problems, the present invention effectively compresses video data from similar videos, extracts feature summary information using data clustering, and extracts sequential patterns through sequential pattern mining. We propose a method to directly extract meaningful patterns. This includes setting a region of interest to reduce the amount of data, removing feature elements that appear in a short time within a frame, extracting only major frames, combining pixels of similar characteristics into logical basic units, and dynamic / static A method of separating motion information based on weights by separating a region, a method of selectively removing overlapping clusters between front and rear frames, and the like is provided, and an object of the present invention is to provide such an integrated system.

Since video data is generally large, the time required for clustering 8 to extract clustered characteristics of the data also increases in proportion to the size of the initial data. Therefore, if the data set is processed in advance and regenerated into a compressed small data set and then clustered (8), more accurate and faster results can be obtained. In particular, since video has a large spatial and temporal redundancy due to its characteristics, the semantic loss of information appearing in the video is minimized by extracting only important information from which redundancy is removed. In addition, since unnecessary noise is often included according to the surrounding environment of a camera or a video generating video, common information between similar videos can be more effectively extracted through a process of refining data.

FIG. 1 illustrates the overall data mining system, and is composed of the following process steps, and all steps except step 1 may be selectively applied according to a user's needs.

Step 1) Extract characteristic log from video data (2)

Step 2) Set up region of interest (4)

Step 3) Extraction of characteristic information applying minimum repeatability (5)

Step 4) Extract Key Frames (6)

Step 5) Clustering (8)

Step 6) Create Inference Block (10)

Step 7) Apply dynamic static domain weights (11)

Step 8) Clustering

Step 9) Generate Sequential Logs

Step 10) Sequential Pattern Mining

Hereinafter, described in detail by the accompanying drawings as follows.

Step 1) Extract characteristic log from video data (2)

The contents of the video are analyzed from the video, separated into frame units that refer to a single instant of still image, and feature information representing a video such as red, green, and blue is extracted for each frame. A video entered during the time the video starts and ends is defined as a transaction, and this video transaction consists of successive frames of the same video.

Characteristic information such as texture and color extracted from the video is merged with a certain number of pixels according to a user's setting in order to reduce the size of data, which is defined as a base block. For example, as shown in FIG. 3, each pixel 15a, 15b, 15c, and 15d is recalculated by arithmetic mean calculation for each video characteristic component value (hereinafter referred to as characteristic information) and merged, and in units of base blocks. It is stored in the log file (3).

In many applications, data is generated in transactional units, which are units of data sets that are generated concurrently and cannot be semantically divided. On the other hand, existing clustering is suitable for modeling data having continuous values, but it is not suitable for creating clusters that reflect the characteristics of transaction data because it does not perform clustering considering transaction concepts. Therefore, in the present invention, a modified clustering technique is applied to reflect the concept of a transaction and extract a cluster from the transaction. A video transaction that introduces the concept of a transaction is regarded as a logical unit from the moment the video starts to the end.

Step 2) Restrict area of interest (4)

As the simplest method of reducing the amount of data to be analyzed in the video data, a region of interest limitation method may be considered, in which only a selective region of interest in the screen space is defined as an analysis target. This method not only reduces the size of the data, but also has the effect of removing unnecessary characteristic information extracted from the uninterested region and degrading the accuracy of the modeling result of the data.

The region of interest and the region of uninterest in the video data are implemented by reading a mapping file of a predetermined type and maintaining or removing the characteristic information values of the base blocks constituting the video data. That is, if the characteristic value V _Bif of the characteristic information f of the base block B _i before application belongs to the region of interest, the characteristic value V ' _Bif to which the region of interest restriction method is applied has the same value but is removed if it is an uninterested region. do.

The video data having the redefined feature values is divided into a region of interest and an uninterested region based on the threshold value 0, and the base block determined as the uninterested region is removed from the set of characteristic values representing the video data to be analyzed. The amount of data can be reduced.

The algorithm is shown in FIG. The relevant variable initialization 19a and the region of interest map loading 20 are initialization parts, a transaction end confirmation block 21 which sequentially loads all transactions until the end of the target video transaction, and all frames in turn until the end of each transaction. In the final frame check block 22 to load and the final base block check block 23 to load all base blocks until the end of each base block, all existing base blocks in the log are sequentially searched and transferred to the next block. In the region of interest check block 24 and the characteristic information removal block 25, the base block of the region of interest is compared with the initialized region of interest map, and the base block included in the region of interest is kept and the log is stored.

For example, if the interest region is set to the shaded area when only the features of the entity A (17a, 17b, 17c, 17d) and the entity B 18 are interested in the characteristics of the entity A (17a, 17b, 17c, 17d), Entity B 18 that is not of interest is excluded from the log.

Step 3) Extraction of characteristic information applying minimum repeatability (5)

In one video transaction, various objects may appear and disappear within the video at each frame that changes over time. The length of time that an entity appears in a single transaction can be used as a criterion for judging the importance of the entity and can be expressed as the number of consecutive frames. In the present invention, when the characteristic information of each base block is maintained as a deviation value within a threshold value in a continuous frame, it is regarded as valid information and defines the minimum number of frames that are effectively informed as the minimum repeatability. This minimum repetition removes the characteristic information lower than the minimum repetition rate such as noise, thereby effectively reducing the amount of video data while maintaining the main information.

The data removal method using the minimum repeatability includes the feature information removal method that removes only the corresponding characteristic information that does not satisfy the minimum repeatability threshold, and the base block when all the characteristic information constituting the base block does not satisfy the minimum repeatability. There is a method of removing a base block to remove itself, and a method of removing a frame if the ratio of the removed base block to a valid base block exceeds a set threshold.

Because the characteristic information removal method removes only a part of all the characteristics expressed by the object, an error may occur in the extracted characteristic information result, while the base block removal method removes all the base blocks in which unnecessary objects such as noise are generated. Can be. In addition, the frame removal method may be a method of effectively removing a frame when vibration or noise occurs in the entire frame.

If the minimum repeatability is not satisfied, such as the feature information removal method and the base block removal method, there is a method of copying the corresponding property information of the previous frame or the value of the base block in addition to removing the corresponding part. Instead of compressing the data, this method modifies using the information of the immediately preceding frame instead of the instantaneous noise information, which has a refinement effect of selecting only the data of the long-exposure object to be noted in the target video.

The algorithm is shown in FIG. The relevant variable initialization 19b and the region of interest map loading 20 are initialization parts, and the video end confirmation block 21, the last frame confirmation block 22, the last base block confirmation block 23, and the last characteristic information confirmation block ( In step 26), the characteristic information of all existing base blocks in the transaction is sequentially searched from the first data to the last data, and the characteristic information change amount determination block 27 compares the characteristic information with the characteristic information of the previous frame. If the characteristic information change amount is larger than the threshold value, the number of times that the characteristic information is repeated within the threshold value is calculated in the characteristic information count determination block. If the characteristic information count is larger than the characteristic information count threshold, the characteristic information is regarded as a valid value and stored. If the characteristic information count is smaller than the characteristic information count threshold, the characteristic information is removed in the characteristic information removing block 29. If the characteristic information change amount is smaller than the threshold, the characteristic information count is incremented by +1 in the characteristic information holding block 30 and proceeds to the next characteristic information. After checking all property information, modify the log and exit.

Step 4) Extract Key Frames (6)

If the number of frames taken per second is high when generating video, the correlation between the frames before and after is high. Therefore, it is effective to select only the key frames that can represent these frames by collecting consecutive frames with little change in characteristic information. This is called. There are various methods for selecting a key frame among the frames composing the transaction, and the present invention introduces a definition of frame differentiation and uses it as a selection criterion.

[Definition 1] Frame Differentiation

The frame difference Δ (F _{i ~} F _j ) between successive frames F _i and F _{j in} the original frames is the absolute value of the difference between the characteristic information of the current frame in the characteristic information of the previous frame of each base block as follows. It is defined as a cumulative value.

This frame difference is changed proportionally according to the amount of change of the characteristic information in the current frame from the previous frame.The difference between the frame and the threshold is extracted by selecting the first frame as the key frame and extracting the frame difference for successive frames. Select the frame that starts to be the new key frame. Such a key frame may be referred to as a frame representing frames having a frame degree of difference below a successive threshold, and this method is used to continuously extract key frames for all frames of the remaining transaction.

For example, in [Figure 5], the first frame F ₀ is always a key frame, and the frame difference is continuously calculated by increasing the frames sequentially from the next. If the frame difference is △ (F ₀ ~) If F ₂ ) exceeds the threshold T _hk , the next key frame becomes F ₂ , and the first key frame F ₀ represents the frame set {F ₀ , F ₁ } and satisfies the following.

△ (F _{i ~} F _j ) <T _{hk where} i = 0 and j = 0, 1

The frame difference is continuously calculated from F ₂ , the second key frame. If T _hk is exceeded in a frame with i = 6, the third key frame becomes F ₆ and the frame set {F ₂ , F ₃ , F ₄ , F ₅ } and the following are satisfied.

△ (F _{i ~} F _j ) <Th _{k where} i = 2 and j = 2, 3, 4, 5

In addition to the threshold T _hk , a new threshold Th _s can be introduced to extract a new representative key frame representing the key frames, which compares the difference between the previous key frame and the current key frame to satisfy the following conditions. Becomes

Δ (F'i _to F'i _{+ 1} ) <Th _{s where} i '= 1, 2,... , n '. n 'is the number of key frames

If Th _s is exceeded in the key frame of i = 3, the representative key frame becomes F ₀ and represents the key frame set {F ₀ , F ₂ , F ₆ }. The key frame uses a cumulative frame disparity, but the representative key frame uses an unaccumulated frame disparity, and thus can be used as a method of finding a sudden change between frames.

Key frames have the effect of selecting only the major frames above the selected threshold after removing frames with much redundancy between screens within all frames of a transaction. Therefore, the key frame can be found in all the frames in the transaction, and then the selected key frame can be selected and saved as a new log file. The log file can be obtained while maintaining the main video characteristics of the original transaction without major loss.

  The algorithm is shown in FIG. The relevant variable initialization 19c and the region of interest map loading 20 are initialization parts, and the transaction end confirmation block 21, the final frame confirmation block 22, the final base block confirmation block 23, and the final characteristic information confirmation block ( In step 26), the characteristic information of all existing base blocks in the transaction is transmitted to the next step. The first key frame is basically the first frame, and the frame difference calculation block 31 accumulates all the characteristic information changes with the previous frame while continuously increasing the frame. If the accumulated characteristic information change amount in the frame difference calculation block is larger than a given key frame threshold, the new group definition block 33 adds the current frame to the key frame list and starts a new group. In the next step, the representative key frame change amount comparison block 34 calculates a difference between the previous key frame, the current key frame, and the characteristic information, and adds the current key frame to the scene list when the representative key frame threshold is exceeded. If not exceeded, it proceeds to a new frame, searches all frames, restores the key frame list and scene list in the log, and exits.

Step 5) Clustering (8)

The preprocessing step can be selectively applied in consideration of the characteristics of the video, and the characteristic information logs through each step can generate a file storing the characteristic information of the transactional videos through clustering, and this file is called a profile. As described above, the existing clustering does not introduce the concept of a transaction, but in the present invention, a transaction that is regarded as one logical unit by a start and end point is grafted, and a plurality of characteristic information of the same base block appearing in one transaction appear. Even if it is, the logical transaction unit is processed as a base, so it is considered as a one-time frequency and modified to be clustered.

In the clustering process, the characteristics information log files in the form of a video transaction, the minimum map and the clustering range representing the frequency of transactions appearing in the total transactions are input. After clustering, the resulting cluster C _j can be expressed as follows using the cluster identifier C _id , base block B _i , characteristic information f, cluster minimum value C _min , cluster maximum value C _max , cluster average value C _ave and cluster support C _sup . have.

C _j = {C _id , B _i , f, C _min , C _max , C _ave , C _sup | 0 ≤ i <(W / φw) * (H / φh)}

The base block ID becomes the ID of the base block according to the coordinates appearing in the frame, which is affected by the merging between the base blocks and the resolution of the video. The cluster minimum value and the cluster maximum value are information representing an area of characteristic information that each cluster may have, and an average of characteristic information generated in such an area is a cluster average value, and cluster support means support of each cluster. Finally, profile P is a collection of clusters {C ₀ , C ₁ , C ₂ ,. , C _d }.

Clustering considers the characteristic information value in a single transaction in units of base blocks and clusters each of them. The clustering range and minimum support are input as parameters, and the clustering range is the maximum difference value of the characteristic information regarded as one cluster, and characteristic information smaller than this range becomes the same cluster. The minimum support is determined by the ratio between the number of transactions in which the characteristic information appears and the total number of transactions. A cluster is created around the characteristic information values that frequently appear as the minimum support increases.

Step 6) Create Inference Block (10)

Since the objects in the video have individual areas and occupy a certain area in the frame, the characteristic information belonging to a specific object becomes similar to the clusters of the same object around it. The base block of the cluster is merged and transformed into one new logical block, which is called an inferred block. This is similar to the characteristic information similarity SBi between the cluster α of the base block B and the clusters β of the other base block B 'as follows. After calculating, the base blocks that are less than the preset merge allowance threshold Th may be merged to generate the same analogy block. At this time, the characteristic information similarity SBi is defined as follows.

In other words, the inference block DBi is a set of all base blocks B _i 'whose SBi satisfies the threshold based on Bi {B _i ' | SB _i <Th}, and the values of clusters a ' _min , a' _max , a ' _ave , and a' _sup of the new inference block are set by arithmetic average of min, max, avg, and sup items of the included clusters. If these are α ' _l , it becomes as follows. Where Ct is the number of elements in DB _i .

In FIG. 8, similar base blocks 36a having the same characteristic information when expressed in units of base blocks are represented by one analogy block 36b, and a plurality of base block sets {B ₀ , B ₁ ,. , B _e } is an example of a simple processing of an inferred block set of {DB ₀ , DB ₁ , DB ₂ }.

By introducing analogy blocks, the redundancy between base blocks with similar characteristic information existing in video characteristics can be eliminated and maintained as one characteristic information, which reduces the amount of data much more than the method of storing the characteristic information of the entire base block. It became possible.

The algorithm is shown in FIG. The associated variable initialization 19d is an initialization portion, and the reference base block check block 38 increments the base block, which is a reference for calculating the difference in the characteristic information between the base blocks. The characteristic information difference calculation block 39 obtains the difference between the base base block and the change base block 39 and stores the difference in the array. This process continues from the change base block check block 40 to the final value of the change base block. When the difference of all the characteristic information is calculated, the minimum difference search block 41 selects the base block having the smallest difference and passes through a threshold check block 42 for checking whether the minimum difference is less than a threshold for merging the base blocks. If it is below the threshold, the base block merging block 43 merges the base blocks, and if it is above the threshold, the process for increasing the next reference base block is repeated.

Step 7) Apply Static and Dynamic Base Block Weights (11)

The video may be divided into a dynamic region in which each base block changes over time and a static region without significant change due to the nature of the video data. Since the static region has a small change, the number of clusters generated is small, whereas the dynamic portion increases the number of clusters. Therefore, when the number of clusters is set as the threshold Th that is a dynamic / static base block classification criterion, the base block including the characteristic information having the number of clusters exceeding Th is regarded as a dynamic base block, and the number of clusters below the threshold is counted. A base block including the characteristic information with may be regarded as a static base block.

Using these characteristics, the static / dynamic base block weight Ω _Bi is obtained by applying the dynamic region weight Sw and the static region weight Dw as follows.

In general, since the static part of the video does not change over all frames, one cluster is generated for each characteristic information, and in a dynamic case, two or more clusters are generated, so Th may be set to 1.

The static / dynamic base block weights are used to distinguish between static base blocks for which objects in the background can be targeted and dynamic base blocks for moving objects according to the user's intention, and to assign importance to each object. It became possible.

In FIG. 11, the relevant variable initialization 19e initializes the related variable and loads a profile including the characteristic information clusters in the profile loading block 44. On the basis of the base block or the inferred block, the block end confirmation block 45 reads the reference block for applying the weight in order. In the cluster number comparison block 46, the threshold is compared with the number of clusters included in the reference block. If the cluster number is higher than the threshold, the dynamic weighting block 47 assigns the dynamic weight to the cluster and static weighting if it is lower than the threshold. In block 48 a static weight is assigned. Repeat this process until the last block.

Step 8) Clustering

The clustering process uses support, which is a value obtained by dividing the number of transactions in which characteristic information appears by the total number of transactions. Support is a criterion that indicates the frequency of appearance of feature information in transactions. By introducing minimum support, only important feature information that satisfies more than the minimum support in clustering is extracted. Therefore, characteristic information that does not satisfy the minimum support is excluded during clustering, and only clusters that are considered as main may be generated by modeling only the characteristic information having a high frequency of appearance above the minimum support. On the other hand, if the generated clusters have similar values, multiple clusters can be merged and expressed as a single simplified cluster. In this case, the maximum similar value range for merging is called a clustering range.

For example, referring to FIG. 12, the characteristic information P1, P2, P3, P4, and P5 shown in the specific baseblock of transaction 1 are distributed and represented in the characteristic information region according to each value, and the characteristic shown in the specific baseblock of transaction 2 Information P1, P2, P3, and P4 are represented in the characteristic information area as transaction 2 according to their respective values. If the minimum support map is set to 0.8, P5 is removed because it does not satisfy the minimum support map, and other clusters included in the clustering range R satisfying the minimum support map are merged with each other to create a cluster. Therefore, the characteristic information clusters included in the final profile are α1, α2, and α3.

After clustering, the resulting cluster αj can be expressed as follows by using the cluster identifier αid, baseblock Bi, characteristic information f, cluster minimum value αmin, cluster maximum value αmax, cluster average value αavg and cluster support αsup. Information files are called profiles.

αj = {αid, Bi, f, αmin, αmax, αavg, αsup | 0 ≤ i <(W / φw) * (H / φh)}

The baseblock Bi is an identifier of the baseblock according to the coordinates in the frame, the cluster minimum value and the cluster maximum value are information indicating an area of characteristic information each cluster can have, and the average of characteristic information generated in these areas is the cluster average value. Cluster support means the support of each cluster. Finally, profile P becomes a set of clusters as follows.

P = {alpha 0, alpha 1, alpha 2,... , αd}

Step 9) Generate Sequential Logs

In order to extract the main patterns of the data appearing sequentially from the video transaction log, first extract only the main data from the log and then generate the sequential patterns. To do this, select only the clusters that appear in the clustering profile among the data of the input log, create a new file, and search for the patterns that appear sequentially in the clusters listed in this file. The sequential log has end of frame and end of transaction identifiers. In the process of generating sequential logs, clusters appearing in transaction logs are often extracted. In this case, an effective method of compressing sequential logs or removing redundant information is required. In the present invention, in order to remove overlapping clusters between successive frames, a technique of removing a cluster newly appearing or disappearing from the current frame is used.

The algorithm is shown in FIG. The relevant variable initialization 49 initializes the related variable and loads a profile including the characteristic information clusters in the profile loading block 44. In the video end acknowledgment block 21, the final frame acknowledgment block 22, the final base block acknowledgment block 23, and the final characteristic information acknowledgment block 26, the characteristic information of all existing base blocks in the transaction is determined from the initial data to the final data. In order to search through the feature information and the cluster comparison block 50 in the same base block and the cluster of the same characteristic information in the profile, if the search is satisfied and proceeds to the next step. In the cluster comparison block 67 and the cluster backup block 68, the cluster output block 51 compares whether or not the current cluster appears in the previous frame. Write to output file. This process is repeated until the final transaction log is read and then terminated.

Step 10) Sequential Pattern Mining

In order to retrieve repetitive sequential patterns from clusters of sequential logs, the present invention uses the Apriori algorithm. The Apriori algorithm is the most basic algorithm that generates all possible sequential combinations from data that occur frequently over time in multiple transactions, and selects and extracts only those combinations that are above a certain frequency. For this process, the Apriori algorithm receives a list of transactions, items that appear in sequence in each transaction, and a minimum map, which is the minimum number of occurrences of each item that must appear in the entire transaction to perform a sequential search. As a result, a combination of clusters appearing at the same time and a combination of these clusters can obtain a sequential pattern appearing over time in a transaction, and these patterns can be stored in a sequential pattern profile for future application.

The algorithm is shown in FIG. The related variable initialization 49 initializes related variables and sequentially searches for a target transaction for extracting a sequential pattern from the transaction list end confirmation block 52. This process reads all clusters one by one through the video end confirmation block 21, the last frame confirmation block 22, and the cluster end confirmation block 53, and then clusters the cluster IDs read from the cluster list update block 54 and the number of occurrences. The list database 55 is stored. After searching the cluster for all transactions, in the least support block 56 and the frame valid cluster extraction block 57, only the critical clusters satisfying the minimum map are selected and the unsatisfactory clusters are removed. Finally, all possible combinations between the clusters are generated, targeting only valid clusters, and this is done in frame valid cluster combination generation block 58. All cluster combinations thus generated become all combinations that can appear in each frame, and are continuously represented by one ID in order to simplify the calculation of subsequent processes in the ID conversion block 59. From the cluster combinations represented by the IDs, the transaction valid cluster combination generation block 60 generates a combination of clusters represented by the IDs that can be generated over time, and the ID restoration block 61 generates the clusters represented by the IDs. Convert to a cluster combination. Finally, the sequence pattern represented by the cluster combination is stored in the sequence pattern file 62.

As described above, the present invention relates to a method of extracting knowledge information from a video. The video signal is decomposed from a video, subjected to a compression and refinement process for data mining, and a feature is analyzed and knowledged using a data mining technique. To make the information extractable. In addition, in order to assist the accuracy of the knowledge information of clustering, it is possible to additionally examine the change of knowledge information with time progress as extraction of the sequential pattern through sequential pattern mining. Such knowledge information is expressed in a reduced size from massive video data, so that it can be effectively stored and managed, and has the advantage that it can be used for various purposes by extracting a specific phenomenon or pattern more effectively than the existing method.

Claims (13)

In a system for extracting knowledge information from a video database, Extracting basic characteristic information necessary to create a profile from the video databases to be subjected to the above step; Generating a region of interest characteristic log file by removing base blocks of an uninterested region so that unnecessary regions of interest are not included after the step to increase an error of a profile; Searching for and removing base blocks that do not satisfy the minimum repeatability to remove the objects appearing for a short time after the step, and generating a minimum repeatability characteristic information log file; Creating group and scene frames from the property information log extracted from the previous step to remove temporal redundancy after the step, and storing the key frames as key frame property information log files; Creating a profile by clustering the key frame characteristic information log file or the final characteristic information log file generated during the preprocessing after the step; After the step of merging base blocks having clusters of similar characteristics in the profile to form a yufu block, Generating a new profile weighted to the dynamic and static cluster after the step; Generating a sequential log by comparing the final clustering profile with the original transaction log after the step; And sequential pattern mining to extract sequential patterns from the sequential logs after the step. A method using any device that enables the capture and storage of a video camera or other video instead of a video database using the method of claim 1. Characteristic information used using the method of claim 1 is a method of using color features including red, green, blue, Y, Cr, Cb, H, S, I A method of using the area of an object, the moving direction of the object, the speed of the object, and the texture as the characteristic information used using the method of claim 1. Base block merging method for inputting the number of horizontal and vertical pixels to be merged using the method of claim 1 as a parameter A method of applying minimum repetition rate using the characteristic information count threshold and the characteristic information change threshold as an input using the method of claim 1 Key frame extraction method using the key frame threshold and the representative key frame threshold as an input using the method of claim 1 Inference block generation method for merging base blocks having characteristic information difference less than a merge allowance threshold value using the method of claim 1 Dynamic, static base block weighting method using the cluster number threshold as input to set the dynamic, static base block weight using the method of claim 1 Clustering method using the method of claim 1 as a clustering range, minimum support Comparing the original transaction log and the clustering profile using the method of claim 1, when generating a sequential log, the cluster appeared in the previous frame and the current cluster newly appeared in the current frame to remove cluster redundancy and increase compression efficiency. Log output method to print to the sequential log only when the cluster is destroyed in the current frame Comparing the new video and the profile obtained using the method of claim 1 or 1 to 11 to calculate the similarity between the two sides, A system for calculating the similarity between the existing clustering profile and the sequential pattern profile that extracts and retains the log from the new video after the above step, and notifies the result by comparing the threshold with a set threshold (FIG. 2). The system of claim 12, wherein the clustering and sequential pattern profiles are pre-generated off-line but output from the new video is accessed online and comparable in real time.

Images