JP2013142961A - Feature point detection program for detecting feature point in image, image processor and method - Google Patents

Abstract

A feature point detection program and the like for determining a pixel at a higher speed in consideration of a determination result of whether or not the pixel is a feature point in an adjacent pixel determined in advance are provided.
A decision tree storage unit prepares a second decision tree for each branch at the end of the nth layer in the first decision tree, and for each branch at the end of the nth layer in the second decision tree. A first decision tree is prepared. A first step of designating one target pixel in the input image and a plurality of peripheral pixels at a predetermined position; and a second type of detecting a luminance type representing a magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel And when a feature point / non-feature point is extracted using the first decision tree for the first pixel of interest, the second pixel of interest adjacent to the first pixel of interest is extracted. And a third step in which feature points / non-feature points are extracted using the second decision tree selected according to the branch at the end of the nth layer in the first decision tree.
[Selection] Figure 4

Description

  The present invention relates to a technique for detecting feature points in an image.

  In recent years, a technique for recognizing or searching an image based on “feature points” representing visual features of a local region in the image has attracted attention. The feature points are represented by, for example, feature quantities of a multidimensional vector. According to this technology, algorithms such as SIFT (Scale-Invariant Feature Transform) and SURF (Speeded Up Robust Features), which are robust to changes in rotation and scale, are widely used. For example, SIFT is a technology that analyzes a characteristic local region using a scale space and describes a multi-dimensional feature quantity that is invariant to scale change and rotation. In particular, according to the technical field of image recognition in augmented reality (AR) applications, since it is necessary to process in real time, it is required to detect feature points faster than SIFT and SURF. .

  Conventionally, there is a technique for determining at high speed whether each pixel is a feature point by using a primary differential value of each point of interest in an image and a secondary differential value in the direction of the primary differentiation and the vertical direction. (For example, refer to Patent Document 1).

  There is also a technique for comparing the luminance of a pixel of interest with the luminance of surrounding pixels and determining whether or not the pixel of interest is a feature point (see, for example, Non-Patent Document 1). According to this technique, when a pixel (or dark pixel) brighter than a certain brightness than the luminance of the pixel of interest has a threshold pixel of N (N> 1) continuous peripheral pixels, the pixel of interest is determined as a feature point. To do.

FIG. 1 is a flowchart for detecting feature points in the prior art.
FIG. 2 is an explanatory diagram showing the positions of a pixel of interest and peripheral pixels in a conventional FAST (Features from Accelerated Segment Test) feature detector.

(S1) First, one target pixel in the input image and a plurality of peripheral pixels at a predetermined position are designated. According to FIG. 2, the pixels located three pixels ahead in the radial direction with the target pixel p as the center are the peripheral pixels x1 to x16.

(S2) Next, a luminance type representing the magnitude relationship of the luminances of the peripheral pixels x1 to x16 with respect to the luminance of the target pixel p is detected. The luminance type is obtained by dividing the luminance of each of the peripheral pixels x1 to x16 with respect to the luminance of the pixel of interest p into three as follows using two threshold values.
Darker / similar / brighter

  Here, when the peripheral pixels classified as darker or brighter continue for N thresholds or more, it is determined that “the target pixel p is a feature point”. In order not to detect a point on the edge as a feature point, the threshold value N is set to 9 according to FIG. For example, if 10 consecutive x1 to x10 (threshold 9 or more) are determined to be bright, the target pixel p is determined to be a feature point.

  Further, there is a technique for speeding up the feature point determination described in Non-Patent Document 1 by using a decision tree (see Non-Patent Documents 2 and 3, for example).

  FIG. 3 is an explanatory diagram showing a decision tree for feature point detection in the prior art.

  According to FIG. 3, the decision tree has peripheral pixels as nodes, branches from each node for each luminance type, and assigns feature points C (Corner) / non-feature points N (Non-Corner) to terminal nodes. is there. FIG. 3 shows a tree with a depth of 4.

(S3) Subsequent to S2 described above, the feature tree C / non-feature point N of the end node is extracted by following the decision tree according to the luminance type in order from the peripheral pixels of the head node. Thus, for example, if the peripheral pixel x5 is normal with respect to the target pixel p and the peripheral pixel x13 is normal with respect to the target pixel p, the result is “N”. It is determined that p is not a feature point. At this time, it is possible to immediately shift to determination of the next pixel of interest.

  Thus, according to the prior art, feature points can be detected at high speed by repeating S1 to S3 for each pixel of interest as shown in FIG.

JP 2009-2111330 A

E. Rosten and T. Drummond, “Fusing points and lines for high performance tracking,” in Proc. Of ICCV, 1508-1515, 2005, [online], [searched on December 13, 2011], Internet <URL: http: //www.arnetminer.org/viewpub.do?pid=293612> E. Rosten and T. Drummond, “Machine learning for high-speed corner detection,” ECCV, 430-443, 2006, [online], [December 13, 2011 search], Internet <URL: http: // www .springerlink.com / content / y11g42n05q626127 / ＞ "Acquisition of knowledge by decision tree and inductive reasoning", [online], [Search on December 13, 2011], Internet <URL: lis2.huie.hokudai.ac.jp/~kurihara/classes/AI/dtree. ppt>

  However, according to the technique described in Patent Document 1, since only the information of the primary differential value and the secondary differential value of the target pixel is used, it is easily affected by noise and cannot be detected robustly. There is. In addition, according to the technique described in Non-Patent Document 2, each pixel is merely determined independently. On the other hand, the inventors consider that many of the feature points in the image are continuously connected and are the feature points for the target pixel in consideration of the determination result of the adjacent target pixel determined in advance. I thought that the process of judging whether or not could be processed at higher speed.

  In view of this, the present invention considers the determination result of the adjacent pixel determined earlier, a feature point detection program, an image processing device, and an image processing device capable of determining at high speed whether or not the pixel of interest is a feature point It aims to provide a method.

According to the present invention, a computer mounted on an image processing apparatus is
A first step of designating one pixel of interest in the input image and a plurality of surrounding pixels at a predetermined position;
A second step of detecting a pixel type representing a relationship between the target pixel and each peripheral pixel;
Using a decision tree storage unit that stores a decision tree that has a neighboring pixel as a node, branches from the node for each pixel type, and adds a feature point / non-feature point to a terminal node, the pixel type in order from the surrounding pixel of the first node And the third step of extracting the feature points / non-feature points of the end node in accordance with the decision tree, and for each pixel of interest, the first step to the third step are repeated. In the feature point detection program,
The decision tree storage unit has a plurality of decision trees, and for each branch at the end of the nth layer in each decision tree, one of the plurality of decision trees is prepared,
For the third step,
When a feature point / non-feature point is extracted using one of a plurality of decision trees for the first pixel of interest,
Feature points / non-feature points are extracted from the second target pixel adjacent to the first target pixel using the decision tree selected according to the branch at the end of the nth layer in the decision tree. The computer is made to function.

  According to another embodiment of the feature point detection program of the present invention, the pixel type is a relationship between the brightness of a predetermined plurality of peripheral pixels with respect to the brightness of the target pixel, and a darker / normal relationship using two threshold values. It is also preferred to run the computer so that it is divided into (similar) / brighter.

  According to another embodiment of the feature point detection program of the present invention, the plurality of decision trees are classified into a plurality of first decision trees and a plurality of second decision trees, and the nth layer in the first decision tree. It is also preferable that a second decision tree is prepared for each branch at the end of the first decision tree, and a first decision tree is prepared for each branch at the end of the nth layer in the second decision tree.

  According to another embodiment of the feature point detection program of the present invention, the peripheral pixels of nodes included in the first decision tree up to the nth layer and the nodes included in the second decision tree up to the nth layer It is also preferable that the computer be executed so that it is different from the peripheral pixels.

According to another embodiment of the feature point detection program of the present invention,
If the pixel of interest is specified in order from left to right for a row and from top to bottom for a column,
The first target pixel switches the decision tree according to the determination result of the branch to the n-th layer in the second target pixel adjacent to the upper side of the first target pixel,
It is also preferable that the second target pixel causes the computer to switch the decision tree according to the determination result of the branch to the n-th layer in the first target pixel adjacent to the left side of the second target pixel.

According to another embodiment of the feature point detection program of the present invention,
The decision tree storage unit sets the nth layer as the second layer,
A second decision tree is prepared for every 9 branches of the second layer of the first decision tree,
It is also preferable that the computer is executed so that the first decision tree is prepared for every nine branches of the second layer of the second decision tree.

According to another embodiment of the feature point detection program of the present invention,
The peripheral pixels of the first layer and the peripheral pixels of the second layer in the first decision tree are located in opposite directions around the target pixel,
The peripheral pixels of the first layer and the peripheral pixels of the second layer in the second decision tree are located in opposite directions around the target pixel,
A line connecting the peripheral pixel of the first layer and the peripheral pixel of the second layer in the first decision tree and a line connecting the peripheral pixel of the first layer and the peripheral pixel of the second layer in the second decision tree It is also preferable to run the computer so that it is substantially perpendicular.

According to another embodiment of the feature point detection program of the present invention,
In order to create the first decision tree and the second decision tree stored in the decision tree storage unit,
A first step of designating one representative pixel in the input learning image;
A pixel of the left side of the representative pixel is set as a pixel of interest, and a second set of pixels derived from the first n neighboring pixels of the pixel of interest is branched to the nth layer of the first decision tree. Steps,
A second n-th peripheral pixel (other than the first n peripheral pixels) in the target pixel is branched to the nth layer of the second decision tree with the pixel above the representative pixel as the target pixel. A third step of deriving a plurality of pixel sets, and repeating from the 01st step to the 03th step for each target pixel,
A plurality of second decision trees are derived using the first plurality of pixel sets, and the computer is executed to derive a plurality of first decision trees using the second plurality of pixel sets. It is also preferable.

  According to another embodiment of the feature point detection program of the present invention, a plurality of second ones are used by using a general supervised learning algorithm using the concept of information entropy from the first / second plurality of pixel sets. It is also preferred to have the computer run to derive the first decision tree.

  According to another embodiment of the feature point detection program of the present invention, it is also preferable that the supervised learning algorithm is executed by the computer so as to be an algorithm of ID3 or C4.5.

According to the present invention, an image processing apparatus having a feature point detection unit,
The feature point detector
Pixel-of-interest specifying means for specifying one pixel of interest in the input image and a plurality of peripheral pixels at a predetermined position;
A luminance type detecting means for detecting a luminance type representing the magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel;
Decision tree storage means for storing a decision tree having a peripheral pixel as a node, branching from the node for each luminance type, and adding a feature point / non-feature point to a terminal node;
Using a decision tree storage means, having a feature point determining means for extracting a feature point / non-feature point of a terminal node by following a decision tree according to the luminance type in order from the peripheral pixels of the head node, and for each pixel of interest In the image processing apparatus that functions to repeat the pixel-of-interest specifying means, the luminance type detecting means, and the feature point determining means,
The decision tree storage means has a plurality of first decision trees and a plurality of second decision trees, and a second decision tree is prepared for each branch at the end of the nth layer in the first decision tree. A first decision tree is prepared for each branch at the end of the nth layer in the second decision tree,
The feature point determination means
When feature points / non-feature points are extracted for the first pixel of interest using the first decision tree,
A feature point / non-feature using a second decision tree selected according to a branch at the end of the nth layer in the first decision tree for a second pixel of interest adjacent to the first pixel of interest It is characterized by extracting points.

According to the present invention,
A first step of designating one pixel of interest in the input image and a plurality of surrounding pixels at a predetermined position;
A second step of detecting a luminance type representing a magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel;
Using a decision tree storage unit that stores a decision tree with a neighboring pixel as a node, branches from the node for each luminance type, and adds a feature point / non-feature point to a terminal node, the luminance type sequentially from the surrounding pixel of the first node And a third step of extracting a feature point / non-feature point of the end node in accordance with the decision tree, and repeating from the first step to the third step for each pixel of interest p A feature point detection method in
The decision tree storage unit has a plurality of first decision trees and a plurality of second decision trees, and a second decision tree is prepared for each branch at the end of the nth layer in the first decision tree. A first decision tree is prepared for each branch at the end of the nth layer in the second decision tree,
For the third step,
When feature points / non-feature points are extracted for the first pixel of interest using the first decision tree,
A feature point / non-feature using a second decision tree selected according to a branch at the end of the nth layer in the first decision tree for a second pixel of interest adjacent to the first pixel of interest A point is extracted.

  According to the feature point detection program, the image processing apparatus, and the method of the present invention, it is possible to determine at high speed whether or not the target pixel is a feature point in consideration of the determination result of the adjacent pixel determined in advance. Can do.

It is a flowchart which detects the feature point in a prior art. It is explanatory drawing showing the position of the attention pixel and peripheral pixel in the FAST feature detector of a prior art. It is explanatory drawing showing the decision tree for the feature point detection in a prior art. It is a functional block diagram of the image processing apparatus in this invention. It is explanatory drawing showing the some 2nd decision tree with respect to the 1st decision tree in this invention. It is explanatory drawing showing the some 1st decision tree with respect to the 2nd decision tree in this invention. It is explanatory drawing showing the position of the surrounding pixel with respect to the attention pixel in this invention. It is explanatory drawing showing having judged the attention pixel in order of the raster scan. It is explanatory drawing showing the position of the adjacent pixel which should use a determination result, when determining an attention pixel.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

  FIG. 4 is a functional configuration diagram of the image processing apparatus according to the present invention.

  According to FIG. 4, the image processing apparatus 1 includes a feature point detection unit 11 and a decision tree generation unit 12. These functional components are realized by executing a program that causes a computer installed in the apparatus to function.

<Feature Point Detection Unit 11>
The feature point detection unit 11 includes a decision tree storage unit 110, a target pixel designation unit 111, a luminance type detection unit 112, and a feature point determination unit 113. Here, the pixel-of-interest specifying unit 111, the luminance type detection unit 112, and the feature point determination unit 113 are repeated for each pixel of interest in the raster scan order.

[Decision Tree Storage Unit 110]
The decision tree storage unit 110 stores a decision tree having peripheral pixels as nodes, branching from each node for each luminance type, and adding a feature point C / non-feature point N to a terminal node. Here, according to the technique described in Non-Patent Document 1, one decision tree is prepared, whereas according to the present invention, a plurality of first decision trees and a plurality of second decisions are made. It is prepared in the following relationship with each other.
A second decision tree is prepared for each branch at the end of the nth layer in the first decision tree.
A first decision tree is prepared for each branch at the end of the nth layer in the second decision tree.

FIG. 5 is an explanatory diagram showing a plurality of second decision trees for the first decision tree in the present invention.
FIG. 6 is an explanatory diagram showing a plurality of first decision trees for the second decision tree in the present invention.

Here, the peripheral pixels of the node included in the first decision tree up to the nth layer are different from the peripheral pixels of the node included in the second decision tree up to the nth layer. Specifically, according to FIGS. 5 and 6, the decision tree is described with the nth layer as the second layer (n = 2), and is prepared in the following relationship.
A second decision tree is prepared every 9 branches of the second layer of the first decision tree.
A first decision tree is prepared for every nine branches of the second layer of the second decision tree.

[Attention pixel designation part 111]
The target pixel designation unit 111 designates one target pixel in the input image and a plurality of peripheral pixels at a predetermined position. According to the present invention, the positions of the peripheral pixels with respect to the target pixel are determined as follows.
The peripheral pixels in the first layer and the peripheral pixels in the second layer in the first decision tree are positioned in opposite directions with the target pixel as the center.
The peripheral pixels of the first layer and the peripheral pixels of the second layer in the second decision tree are located in opposite directions with the target pixel as the center.
As a result, a line connecting the peripheral pixels of the first layer and the peripheral pixels of the second layer in the first decision tree and a peripheral pixel of the first layer and the peripheral pixels of the second layer in the second decision tree are connected. The line is almost perpendicular.

  FIG. 7 is an explanatory diagram showing the positions of peripheral pixels with respect to the target pixel in the present invention.

According to FIG. 7, for example, it is determined as follows.
The first-layer peripheral pixel x1 and the second-layer peripheral pixel x9 in the first decision tree are located in opposite directions with the target pixel as the center.
The first-layer peripheral pixel x5 and the second-layer peripheral pixel x13 in the second decision tree are positioned in opposite directions with the target pixel as the center.
In this way, by alternately determining the nodes on the diagonal line, it is possible to reject the target pixel that is not a feature point at high speed.

  Assume that the first pixel of interest p1 and the second pixel of interest p2 are adjacent on the left and right. At this time, the left and right peripheral pixels x5 and x13 of the first target pixel p1 are adjacent to the left and right peripheral pixels x5 and x13 of the second target pixel p2, respectively. In the case of an image, generally, adjacent pixels have a high correlation. Therefore, the information obtained from the same left and right peripheral pixels x5 and x13 for the adjacent target pixel is small. Therefore, according to the present invention, the decision tree to be switched next to the decision tree for determining the upper and lower neighboring pixels x1 and x9 of the first pixel of interest at the upper level is the left and right neighboring pixels x5 and x13 of the second pixel of interest. Is determined at the top.

[Luminance type detection unit 112]
The luminance type detection unit 112 detects a luminance type representing the magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel (similar to S2 in FIG. 1). The luminance type is obtained by dividing the luminance of each of the peripheral pixels x1 to x16 with respect to the luminance of the target pixel p into three as follows using two threshold values th1 and th2.
Darker / similar / brighter
I: Brightness value of the target pixel
Ip: luminance value of the pth peripheral pixel xp
Ip> I + th1: brighter
I + th1 ≧ Ip ≧ I−th2: Similar
I-th2> Ip: darker

[Feature point determination unit 113]
The feature point determination unit 113 uses the decision tree storage unit 110 to follow the decision tree in order from the peripheral pixel of the head node according to the luminance type, and extracts the feature point C / non-feature point N of the end node. Here, when the feature point determination unit 113 extracts feature points / non-feature points from the first target pixel using the first decision tree, the second feature point adjacent to the first target pixel is extracted. Feature points / non-feature points are extracted using the second decision tree selected according to the branch at the end of the n-th layer in the first decision tree for the target pixel.

  According to FIG. 5, when feature points / non-feature points are extracted for the first pixel of interest p 1 using the first decision tree (x 1-> x 9->...) The second decision tree (2) selected according to the branch at the end of the second layer (x1-> x9) in the first decision tree for the second pixel of interest p2 adjacent to the right side of the pixel of interest p1 Feature points / non-feature points are extracted using x5-> x13->.

  Next, according to FIG. 6, when a feature point / non-feature point is extracted for the second pixel of interest p2 using the second decision tree (x5-> x13->...). The third target pixel p3 adjacent to the lower side of the second target pixel p2 is selected according to the branch at the end of the second layer (x5-> x13) in the second decision tree. Feature points / non-feature points are extracted using the decision tree (x1-> x9->...).

  According to FIG. 5 and FIG. 6, the next decision tree is switched according to the branch at the end up to the second layer (n = 2). That is, the next decision tree is switched based on a decision tree having a relatively shallow hierarchy. Of course, since there are 53 nodes, 53 decision trees can be created. However, when the next decision tree is switched based on a deep decision tree, the number of nodes increases exponentially, which is not realistic. For this purpose, according to the present invention, the next decision tree is switched according to a branch based on a relatively shallow hierarchy of which node has passed in the middle, not which node has finally been reached.

  It is also possible to create a dedicated decision tree according to the branch at the end of the nth layer. However, the amount of calculation processing for creating a dedicated decision tree becomes enormous and is not realistic. Therefore, according to the present invention, the branch of the shallow hierarchy of the decision tree is fixed heuristically. This makes it possible to share information about which node has been passed among a plurality of decision trees.

FIG. 8 is an explanatory diagram showing that the target pixel is determined in the order of raster scanning.
FIG. 9 is an explanatory diagram showing the positions of adjacent pixels that should use the determination result when determining the target pixel.

The raster scan order means, for example, a case where the target pixel is designated in order from left to right for a row and from top to bottom for a column. Here, the decision tree is switched for each pixel of interest as follows.
The first target pixel switches the decision tree according to the determination result of the branch to the n-th layer in the second target pixel adjacent to the upper side of the first target pixel.
The second target pixel switches the decision tree according to the determination result of the branch to the n-th layer in the first target pixel adjacent to the left side of the second target pixel.

<Decision Tree Generation Unit 12>
The decision tree generation unit 12 generates a first decision tree and a second decision tree by inputting a large amount of learning images. The decision tree generation unit 12 includes a representative pixel specification unit 121, a first pixel set derivation unit 122, a first pixel set storage unit 123, a second pixel set derivation unit 124, and a second pixel set storage. Unit 125, first decision tree deriving unit 126, and second decision tree deriving unit 127. Here, the decision tree generation unit 12 is executed to repeat the representative pixel specification unit 121, the first pixel set derivation unit 122, and the second pixel set derivation unit 124.

  The representative pixel specifying unit 121 specifies one representative pixel in the input learning image.

  The first pixel set deriving unit 122 uses the pixel on the left side of the representative pixel as a target pixel, and branches the first n peripheral pixels in the target pixel to the nth layer of the first decision tree. A plurality of pixel sets are derived. For example, for each target pixel, classification determination of x1 and x9 is executed for the pixel on the left side of the target pixel, and the determination result of nine classifications is output to the first pixel set storage unit 123.

  The first pixel set storage unit 123 stores the pixel sets for each classification output from the first pixel set derivation unit 122.

  The second pixel set deriving unit 124 sets the pixel above the representative pixel as a target pixel, and uses the second decision tree for the second n peripheral pixels (other than the first n peripheral pixels) in the target pixel. A second plurality of pixel sets branched to the n-th layer is derived. For example, for each target pixel, classification determination of x5 and x13 is executed for the pixel above the target pixel, and the determination result of nine classifications is output to the second pixel set storage unit 125.

  The second pixel set storage unit 125 stores the pixel sets for each classification output from the second pixel set derivation unit 124.

  The first decision tree deriving unit 126 derives a plurality (9) of second decision trees using the first plurality of pixel sets (9 classifications). The second decision tree is output to decision tree storage unit 110.

  The second decision tree deriving unit 127 derives a plurality (9) of first decision trees using the second plurality of pixel sets (9 classifications). The first decision tree is output to decision tree storage unit 110.

  The first decision tree deriving unit 126 and the second decision tree deriving unit 127 use a general supervised learning algorithm using the concept of information entropy from the first / second plural pixel sets. It is also preferable to derive the second / first decision tree. “Information entropy” is considered as “event uncertainty”, and the decrease in uncertainty due to certain information is considered as “information amount” of the information. The relative value of uncertainty before and after receiving information is called “information entropy”. The “supervised algorithm” inputs a large number of pairs of input data and output data (teacher data, training data), thereby creating a machine (function) that obtains output data for the input data. Thereafter, output data that is not in the past can be obtained as accurately as possible by using a previously created machine.

  As a supervised learning algorithm, for example, there is an algorithm of ID3 or C4.5. ID3 (Iterative Dichotomiser 3) is a general-purpose supervised learning algorithm using the concept of information entropy, determines an event based on a minimum hypothesis, and outputs the decision tree. In this method, the expected value of the average information amount in the case where the value of the variable is determined for each independent variable is obtained, and the operation of making the largest one among them the tree node is recursively executed. C4.5 is an extension of the ID3 algorithm, which can generate a decision tree for classification and is considered a statistical class classifier.

  As described above in detail, according to the feature point detection program, the image processing apparatus, and the method of the present invention, whether the pixel of interest is a feature point in consideration of the determination result of the adjacent pixel determined in advance. Whether or not can be determined at higher speed.

  Various changes, modifications, and omissions of the above-described various embodiments of the present invention can be easily made by those skilled in the art. The above description is merely an example, and is not intended to be restrictive. The invention is limited only as defined in the following claims and the equivalents thereto.

DESCRIPTION OF SYMBOLS 1 Image processing apparatus 11 Feature point detection part 110 Decision tree memory | storage part 111 Attention pixel designation | designated part 112 Luminance classification detection part 113 Feature point determination part 12 Decision tree generation part 121 Representative pixel designation part 122 1st pixel set derivation part 123 1st Pixel set storage unit 124 second pixel set derivation unit 125 second pixel set storage unit 126 first decision tree derivation unit 127 second decision tree derivation unit

Claims (12)

The computer installed in the image processing device
A first step of designating one pixel of interest in the input image and a plurality of surrounding pixels at a predetermined position;
A second step of detecting a pixel type representing a relationship between the target pixel and each peripheral pixel;
Using a decision tree storage unit that stores the decision tree in which the neighboring pixel is a node, branches from the node for each pixel type, and feature points / non-feature points are assigned to terminal nodes, in order from the neighboring pixel of the first node A third step of extracting a feature point / non-feature point of the end node by following the decision tree according to the pixel type, and repeating the first step to the third step for each target pixel. In the feature point detection program to be executed by
The decision tree storage unit has a plurality of decision trees, and for each branch at the end of the nth layer in each decision tree, one of the plurality of decision trees is prepared,
For the third step,
When a feature point / non-feature point is extracted with respect to the first target pixel using any one of the plurality of decision trees,
For a second pixel of interest adjacent to the first pixel of interest, feature points / non-feature points are extracted using the decision tree selected according to the branch at the end of the nth layer in the decision tree. A feature point detection program for causing a computer to function as described above.   The pixel type is obtained by classifying the luminance relationship of a plurality of predetermined peripheral pixels with respect to the luminance of the pixel of interest into darker / similar / brighter using two threshold values. 2. The feature point detection program according to claim 1, wherein the computer is executed as described above.   The plurality of decision trees are classified into a plurality of first decision trees and a plurality of second decision trees, and a second decision tree is prepared for each branch at the end of the nth layer in the first decision tree. The feature point detection program according to claim 2, wherein a first decision tree is prepared for each branch at the end of the nth layer in the second decision tree.   The computer is executed so that the peripheral pixels of the nodes included in the first decision tree up to the nth layer and the peripheral pixels of the nodes included in the second decision tree up to the nth layer are different. The feature point detection program according to claim 3. If the pixel of interest is specified in order from left to right for a row and from top to bottom for a column,
The first target pixel switches the decision tree according to the determination result of the branch to the n-th layer in the second target pixel adjacent to the upper side of the first target pixel,
The second target pixel is characterized in that the computer is executed so as to switch a decision tree according to a determination result of branching to the n-th layer in the first target pixel adjacent to the left side of the second target pixel. The program according to claim 4. The decision tree storage unit sets the nth layer as the second layer,
A second decision tree is prepared for every 9 branches of the second layer of the first decision tree,
6. The feature point detection program according to claim 5, wherein the computer is executed so that the first decision tree is prepared every nine branches of the second layer of the second decision tree. The peripheral pixels of the first layer and the peripheral pixels of the second layer in the first decision tree are located in opposite directions around the target pixel,
The peripheral pixels of the first layer and the peripheral pixels of the second layer in the second decision tree are located in opposite directions around the target pixel,
A line connecting the peripheral pixel of the first layer and the peripheral pixel of the second layer in the first decision tree and a line connecting the peripheral pixel of the first layer and the peripheral pixel of the second layer in the second decision tree 7. The feature point detection program according to claim 6, wherein the computer is executed so as to be substantially perpendicular. In order to create the first decision tree and the second decision tree stored in the decision tree storage unit,
A first step of designating one representative pixel in the input learning image;
A second pixel for deriving a first plurality of pixel sets obtained by branching the first n neighboring pixels of the pixel of interest to the nth layer of the first decision tree with the pixel on the left side of the representative pixel as the pixel of interest. And the steps
The second n neighboring pixels (other than the first n neighboring pixels) of the pixel of interest are branched to the nth layer of the second decision tree with the pixel above the representative pixel as the pixel of interest. A third step of deriving a plurality of pixel sets of 2, and for each pixel of interest, the steps from the 01st step to the 03th step are repeated,
A plurality of second decision trees are derived using the first plurality of pixel sets, and the computer is executed to derive a plurality of first decision trees using the second plurality of pixel sets. 8. The feature point detection program according to claim 1, wherein   Running a computer to derive a plurality of second / first decision trees from a first / second plurality of pixel sets using a general supervised learning algorithm using the concept of information entropy The feature point detection program according to claim 8.   The feature point detection program according to claim 9, wherein the supervised learning algorithm is executed by a computer so as to be an algorithm of ID3 or C4.5. An image processing apparatus having a feature point detection unit,
The feature point detector
Pixel-of-interest specifying means for specifying one pixel of interest in the input image and a plurality of peripheral pixels at a predetermined position;
A luminance type detecting means for detecting a luminance type representing the magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel;
Decision tree storage means for storing a decision tree having the peripheral pixel as a node, branching from the node for each luminance type, and adding a feature point / non-feature point to a terminal node;
Using the decision tree storage means, and following the decision tree according to the luminance type in order from the surrounding pixels of the first node, and feature point determination means for extracting feature points / non-feature points of the end node, and the target pixel In each image processing device that functions to repeat the pixel-of-interest specifying unit, the luminance type detecting unit, and the feature point determining unit,
The decision tree storage means has a plurality of first decision trees and a plurality of second decision trees, and a second decision tree is prepared for each branch at the end of the nth layer in the first decision tree. A first decision tree is prepared for each branch at the end of the nth layer in the second decision tree,
The feature point determination means includes
When feature points / non-feature points are extracted for the first pixel of interest using the first decision tree,
A feature point / non-feature using a second decision tree selected according to a branch at the end of the nth layer in the first decision tree for a second pixel of interest adjacent to the first pixel of interest An image processing apparatus having a feature point detection unit that extracts points. A first step of designating one pixel of interest in the input image and a plurality of surrounding pixels at a predetermined position;
A second step of detecting a luminance type representing a magnitude relationship of the luminance of each peripheral pixel with respect to the luminance of the target pixel;
Using a decision tree storage unit that stores the decision tree in which the neighboring pixel is a node, branches from the node for each luminance type, and feature points / non-feature points are assigned to terminal nodes, in order from the neighboring pixel of the first node A third step of extracting a feature point / non-feature point of a terminal node by tracing the decision tree according to the luminance type, and repeating from the first step to the third step for each pixel of interest p. A feature point detection method in an image processing apparatus,
The decision tree storage unit includes a plurality of first decision trees and a plurality of second decision trees, and a second decision tree is prepared for each branch at the end of the nth layer in the first decision tree. A first decision tree is prepared for each branch at the end of the nth layer in the second decision tree,
For the third step,
When feature points / non-feature points are extracted for the first pixel of interest using the first decision tree,
A feature point / non-feature using a second decision tree selected according to a branch at the end of the nth layer in the first decision tree for a second pixel of interest adjacent to the first pixel of interest A feature point detection method characterized in that points are extracted.

Images