KR20180015570A - Apparatus and method for processing image pair obtained from a stereo camera - Google Patents

Abstract

An apparatus of processing an image pair is capable of generating a target region, including a subject, from each of a first frame image and a second frame image of an image pair and extracting one or more feature points from the generated target region. The apparatus of processing an image pair is capable of connecting the feature points based on a spatial distance of the feature points to generate a tree having the feature points as nodes. Also, the apparatus of processing an image pair is capable of determining cost required when matching a feature point corresponding to a node with respect to a plurality of frame images, and capable of accumulating cost determined for each node according to a branch of the tree. The apparatus of processing an image pair is capable of determining a disparity of a feature point based on a result of accumulating the cost. The determined disparity can be used for determining a distance between the subject and a stereo camera that photographs an image pair. Further, the apparatus of processing an image pair is capable of tracking a position of the subject commonly included in a plurality of image pairs sequentially photographed according to a time.

Description

[0001] APPARATUS AND METHOD FOR PROCESSING IMAGE PAIR OBTAINED FROM A STEREO CAMERA [0002]

The following embodiments are directed to an apparatus and method for processing an image pair obtained from a stereo camera.

Human vision is one of the senses for obtaining the information of the surrounding environment, and it can be recognized that the position of the object is far and near through the binocular. The human brain can determine the distance of visible objects by composing them into one distance information from the visual information coming in through the binocular. The stereo camera system is a system in which the above-described visual function of a person is implemented by a machine. A stereo camera system can perform stereo matching on image pairs obtained using two cameras. The stereo camera system can determine the binocular parallax of the subject included in the photographed image through stereo matching and determine the binocular disparity map for all pixels or objects in the image.

According to one embodiment, in each of a first frame image and a second frame image of an image pair obtained from a stereo camera that photographs a subject, creating a target area including the subject, extracting feature points in the target area Calculating a parallax of the feature point by matching the feature point extracted from the first frame image and the feature point extracted from the second frame image and calculating the parallax of the feature point based on the parallax of the feature point, And determining a distance between the stereo cameras.

According to one embodiment, the calculating step comprises concatenating feature points of the first frame image based on a horizontal distance, a vertical distance or an Euclidean distance between the feature points of the first frame image, Generating a first tree having feature points of a frame image as nodes, connecting feature points of the second frame image based on a horizontal distance, a vertical distance, or an Euclidean distance between the feature points of the second frame image Generating a second tree having feature points of the second frame image as nodes and calculating a parallax of feature points of the first frame image and feature points of the second frame image, And matching the nodes of the second tree and the nodes of the second tree.

According to one embodiment, the matching step comprises accumulating the costs of matching the nodes of the first tree and the nodes of the second tree along the branches of the nodes of the first tree, And determining the parallax of the feature point of the first frame image and the feature point of the second frame image based on the cost, wherein the cost is determined based on the node of the first tree and the second There is provided an image fair processing method which is determined based on luminance and parallax of a node of a tree.

According to one embodiment, the step of determining a parallax range associated with the subject based on a luminance difference between a corresponding region of the second frame image determined according to the target region of the first frame image and the position of the target region A method of processing an image pair is provided.

According to an embodiment, the step of calculating the parallax of the feature point may include an image pair process for matching feature points extracted from the first frame image and feature points extracted from the second frame image within the determined disparity range Method is provided.

According to one embodiment, the step of determining the parallax range comprises the steps of parallel shifting the corresponding area of the second frame image and comparing the luminance of the corresponding area of the parallel area and the target area of the first frame image There is provided an image pair processing method including the steps of:

According to one embodiment, there is provided a method of generating a feature value, the method comprising: extracting a feature value of the target area; generating a feature value plane of the image pair based on the extracted feature value; Comparing the feature value plane model generated from the plane with the feature value plane and determining the position of the object in the image pair based on a result of comparing the feature value plane model with the feature value plane, A method of processing an image pair is provided.

According to one embodiment, there is provided an image fair processing method, further comprising changing the feature value plane model based on the determined position of the subject.

According to one embodiment, there is provided a computer program product comprising a memory in which an image pair photographed by a subject is stored, and a processor for processing the image pair, wherein in each of a first frame image and a second frame image of the image pair, Extracting feature points in the target area, matching the feature points extracted in the first frame image and the feature points extracted in the second frame image, and calculating a parallax of the feature points And determines a distance between the subject and the stereo camera based on the parallax of the feature point.

According to one embodiment, the processor is further configured to determine, based on the cost of matching a first tree having feature points of the first frame image as nodes and a second tree of feature points of the second frame image as nodes A feature point of the first frame image, and a feature point of the second frame image.

According to one embodiment, the processor determines the cost using the similarity determined based on the luminance and the parallax of the feature point corresponding to the node of the first tree and the feature point corresponding to the node of the second tree An image pair processing apparatus is provided.

According to one embodiment, each of the first tree and the second tree is generated by connecting feature points of the first frame image having the smallest spatial distance and feature points of the second frame image having the smallest spatial distance Is provided.

According to one embodiment, the processor determines a parallax range associated with the subject based on a luminance difference between a corresponding region of a second frame image determined according to a target region of the first frame image and a position of the target region An image pair processing apparatus is provided.

According to one embodiment, the processor is provided with an image pair processing apparatus for matching feature points extracted from the first frame image and feature points extracted from the second frame image within the determined disparity range.

According to one embodiment, the processor is configured to extract a feature value of the target area, generate a feature value plane of the image pair based on the extracted feature value, and generate a feature value plane of the image pair obtained before the image pair An image pair that determines the position of the subject in the image pair based on a result of comparing the feature value plane model generated from the feature value plane and the feature value plane, Processing apparatus is provided.

1 is a conceptual diagram for explaining a structure of an image pair processing apparatus according to an embodiment.
2 is an exemplary diagram for explaining an operation of an image-pair processing apparatus according to an embodiment for generating a target area in a frame image and determining a parallax range of the object using the generated target area.
3 is a graph showing the luminance difference calculated from the example of FIG. 2 by the image pair processing apparatus according to one embodiment.
4 is an exemplary diagram for explaining an operation in which an image pair processing apparatus according to an embodiment determines feature points in a target area.
5 is an exemplary diagram illustrating an operation in which an image pair processing apparatus according to an embodiment generates a minimum tree.
6 is a graph showing the results of a comparative experiment for AD, census, and AD + census.
FIG. 7 is a diagram for explaining an operation of determining an image pair processing apparatus according to an embodiment, the distance between a subject and a stereo camera included in an image pair. FIG.
Fig. 8 is a flowchart for explaining an operation of an image-pair processing apparatus according to an embodiment for tracking the position of an object commonly included in a plurality of image pairs.
9 is a graph showing a distribution of response values calculated by fitting an image plane processing apparatus according to an embodiment to a feature value plane model.

Specific structural or functional descriptions of embodiments are set forth for illustration purposes only and may be embodied with various changes and modifications. Accordingly, the embodiments are not intended to be limited to the specific forms disclosed, and the scope of the disclosure includes changes, equivalents, or alternatives included in the technical idea.

The terms first or second, etc. may be used to describe various elements, but such terms should be interpreted solely for the purpose of distinguishing one element from another. For example, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component.

It is to be understood that when an element is referred to as being "connected" to another element, it may be directly connected or connected to the other element, although other elements may be present in between.

The singular expressions include plural expressions unless the context clearly dictates otherwise. In this specification, the terms "comprises ", or" having ", and the like, are used to specify one or more of the described features, numbers, steps, operations, elements, But do not preclude the presence or addition of steps, operations, elements, parts, or combinations thereof.

Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art. Terms such as those defined in commonly used dictionaries are to be interpreted as having a meaning consistent with the meaning of the context in the relevant art and, unless explicitly defined herein, are to be interpreted as ideal or overly formal Do not.

Hereinafter, embodiments will be described in detail with reference to the accompanying drawings. Like reference symbols in the drawings denote like elements.

1 is a conceptual diagram for explaining a structure of an image pair processing apparatus according to an embodiment. The image pair processing apparatus according to one embodiment may be applied to a vehicle, a robot, a smart wearing equipment, a computer terminal or a mobile terminal.

Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a stereo camera 101 for photographing a subject at different angles to receive an image pair. According to another embodiment, the image pair processing apparatus may be connected to the stereo camera 101 via a wired network or a wireless network, and may receive and store the image pair acquired by the stereo camera 101. [

The stereo camera 101 may include a plurality of image sensors that photograph the same object. The two image sensors may be spaced apart by a certain distance. Each of the image sensors can photograph a subject to generate a frame image, and the stereo camera 101 can output a pair (image pair) of frame images according to the time when the subject is photographed. Hereinafter, it is assumed that the stereo camera 101 includes a first image sensor and a second image sensor that photograph a subject at different angles, similar to two eyes of a person. Each of the first image sensor and the second image sensor may photograph a subject to output a first frame image and a second frame image.

Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a target area generator 102 for generating, in each of a first frame image and a second frame image of an image pair, a target area including a subject have. The target area generator 102 may generate a target area of the first frame image including a portion including the subject in the first frame image. Similarly, the target area generator 102 may generate a target area of a second frame image that includes a portion in which the subject is included in the second frame image. The shape of the target area may be polygonal or circular, and may be determined in consideration of the shape of the subject.

Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a feature point extractor 103 for extracting feature points in a target area. Feature point extractor 103 may extract feature points for all frame images of the image pair. The feature point may be selected as a pixel in the target area that facilitates matching of the plurality of frame images. Matching of a plurality of frame images means an operation of processing a plurality of frame images so as to identify a pixel, a subject, and a background common to a plurality of frame images.

Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a feature point connector 107 connecting feature points of each of a plurality of frame images. Feature point connector 107 may connect feature points based on the spatial distance between feature points. Feature point connector 107 may connect feature points in a target area of each of a plurality of frame images to generate a connection graph.

Referring to FIG. 1, an image pair processing apparatus according to an exemplary embodiment may include a matching cost measurer 104 for measuring a cost when matching feature points of a plurality of frame images. The matching cost measurer 104 may measure the cost of matching feature points using the connection graph generated by the feature point connector 107. [ The matching cost measurer 104 may accumulate the measured costs at each of the feature points based on the connection graph.

More specifically, with reference to FIG. 1, an image pair processing apparatus according to an embodiment may include a minimum tree generator 108 that generates a minimum tree from a connection graph. The minimum tree may be created for each of the target regions of the plurality of frame images and may include all feature points within the target region as nodes of the minimum tree. An example of a minimal tree is a minimum cost spanning tree. The matching cost measurer 104 may accumulate the measured costs at each of the feature points based on the minimum tree generated by the minimum tree generator 108. [ More specifically, the matching cost measurer 104 determines the cost of matching the feature points corresponding to each node in the minimum tree with all the feature points as nodes, and then accumulates the determined cost along the branches of the nodes have. That is, the matching tree 104 accumulates costs along the minimum tree, so that a minimum tree with a reduced branch than the connection graph generated by the feature point connector 107 can be used. Therefore, the amount of calculation required when accumulating costs can be reduced.

In the process of measuring the cost when the matching cost measurer 104 matches feature points, the parallax range of the subject can be utilized. Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a parallax range determiner 109 for determining a parallax range associated with a subject, based on a luminance difference of target areas of a plurality of frame images. The parallax range determiner 109 identifies, for the target area of the specific frame image of the image pair, a corresponding area having the same height, shape and size as the target area of the specific frame image in the other frame image, It is possible to determine the difference value of the luminance of the corresponding region of the region and the other frame image. The parallax range determiner 109 can determine the parallax range of the subject based on the minimum luminance difference value. The matching cost measurer 104 may match feature points based on the determined disparity range. Thus, the speed of measuring the cost when matching feature points can be improved.

Referring to FIG. 1, an image pair processing apparatus according to an embodiment may include a feature point disparity calculator 105 that calculates a disparity of a feature point based on accumulated costs. The feature point time difference calculator 105 can determine the time difference that minimizes the accumulated cost as the time difference of the feature point. Feature point disparity calculator 105 can determine the disparity of all feature points in the target area.

1, an image pair processing apparatus according to an embodiment includes a subject distance determiner 106 that determines a distance between a subject and a stereo camera 101, based on the parallax of each of the feature points in the target area . The subject distance determiner 106 can perform alarm processing or operational treatment based on the distance between the determined subject and the stereo camera 101. [

Referring to FIG. 1, an image pair processing apparatus according to an exemplary embodiment may include a subject tracker 110 for tracking the position of a subject in a plurality of image pairs sequentially obtained over time. Every time a newly acquired image pair is input from the stereo camera 101, the subject tracker 110 can determine the position of the subject of the newly acquired image pair based on the result of tracking the subject in an image pair entered in the past have.

The structure of the image pair processing apparatus shown in FIG. 1 is conceptual and includes a target area generator 102, a feature point extractor 103, a matching cost measurer 104, a feature point time difference calculator 105, The feature point connector 107, the minimum tree generator 108, the disparity range determiner, and the object tracker 110 may be implemented as one or more single-core processors or multi-core processors. The illustrated target region generator 102 to subject tracker 110 may be implemented as a combination of one or more processors and memories.

2 is an exemplary diagram for explaining an operation of an image-pair processing apparatus according to an embodiment for generating a target area 210 in a frame image and determining a parallax range of a subject using the generated target area 210 to be.

The parallax means a difference in horizontal coordinate of an image of a subject included in each of two frame images in two frame images generated by photographing the same subject in two image sensors spaced by a certain distance in the horizontal direction. In the image pair obtained from the stereo camera 101 of Fig. 1, the parallax means a difference in the position of the subject included in each of the first frame image and the second frame image.

When the object image of the first frame image is moved in parallel on a pixel-by-pixel basis, the parallel-shifted object image of the first frame image is a pair of frame images obtained by photographing the same subject, Lt; / RTI > Referring to FIG. 2, the image pair processing apparatus can perform parallel movement in units of a target area 210 slightly wider than the subject (in the case of FIG. 2, the car).

Hereinafter, it is assumed that the image pair processing apparatus has created the target area 210 from the first frame image (for example, the left image obtained from the left camera in the stereo camera). The image pair processing device may generate a second frame image 220 corresponding to the target area 210 (e.g., the right side of the stereo camera 220) based on the coordinates on the first frame image of the target area 210 of the first frame image (Hereinafter, referred to as a corresponding region of the target region 210) of the target region 210 (the right image obtained from the camera).

The image pair processing apparatus can translate the corresponding region based on the coordinates of the target region 210 to generate a plurality of corresponding regions. For example, the image pair processing apparatus may move an area of the second frame image 220 having the same coordinates and size as the target area 210 by k pixels in the horizontal direction (for example, positive direction of the x axis) , So that the corresponding region k can be generated. Thus, the coordinates of the target area 210 and the corresponding area k may differ by k pixels. Since the target area 210 is set as the area including the subject, a plurality of corresponding areas may include the subject.

The image pair processing apparatus can determine the parallax range associated with the subject based on the generated difference of the plurality of corresponding regions and the target region 210. [ The difference between the position of the corresponding region and the position of the target region 210 that minimizes the luminance difference may be the parallax of the subject. The parallax range may include the parallax of the corresponding area and the target area 210 that minimize the luminance difference. For example, if the difference in luminance between the corresponding region? And the target region 210 is minimal, the parallax range may include?, Which is the degree to which the corresponding region? Has moved parallel to the position of the target region 210. [

Referring to FIG. 2, the image pair processing device may translate corresponding regions of the second frame image 220 along sweep lines 230 and 240. The sweep lines 230 and 240 may be determined as a horizontal axis of the second frame image 220 or a line parallel to the x axis. The vertical or y coordinate of the sweep lines 230 and 240 may be determined based on the vertical or y coordinate on the first frame image of the target area 210. [ The image pair processing device can adjust the degree of parallel movement of the corresponding area along the sweep lines 230 and 240 from 0 pixels to below the horizontal length of the second frame image 220. [ For example, the image pair processing apparatus can generate 101 corresponding regions by moving the corresponding region from 0 pixels to 100 pixels along the sweep lines 230 and 240. Alternatively, the image pair processing apparatus may generate 257 corresponding regions by moving corresponding regions from 0 pixels to 256 pixels along the sweep lines 230 and 240.

When the corresponding region is moved in parallel by a pixel unit around the position of the target region 210, the parallax range can be determined as a section of the pixel where the corresponding region can move. For example, referring to FIG. 2, the parallax range [0, 100] may be set such that the corresponding region can move from 0 to 100 pixels along the sweep lines 230, 240 with respect to the position of the target region 210 it means. The image-pair processing apparatus according to one embodiment can determine the difference in luminance between the target region 210 and each of a plurality of corresponding regions within the parallax range [0, 100].

FIG. 3 is a graph 300 showing the luminance difference calculated from the example of FIG. 2 by the image pair processing apparatus according to one embodiment. Referring to FIG. 3, the abscissa represents the parallax, that is, the degree of parallel movement of the corresponding region with respect to the position of the target region in pixel units. And the vertical axis represents the luminance difference between the corresponding area of the second frame image and the target area of the first frame image. The shape of the curve of the graph 300 may be a parabola with the opening up. The image pair processing apparatus can identify the time difference Dopt at which the luminance difference is minimum. A portion of the second frame image included in the corresponding region Dopt shifted by Dopt may best match the target region than that of the remaining corresponding region.

The image pair processing apparatus can calculate the disparity range [minD, maxD] including Dopt based on Equation (1) and Equation (2).

In Equations (1) and (2), && means an AND condition operator, and max_disparity means the degree to which the image pair processing apparatus moves the corresponding region to the maximum parallel. The difference (d) means a luminance difference between the corresponding region d and the target region. Equations (1) and (2) are exemplary mathematical expressions, and coefficients or thresholds applied to the luminance difference may be set to different values. An image pair processing apparatus according to an embodiment can use sampling to determine a luminance difference between a corresponding region and a target region.

3, the parallax range [minD, maxD] finally calculated by the image pair processing apparatus is a range [0, 100] in which the image pair processing apparatus calculates the parallax range [minD, maxD] ]. The image pair processing apparatus uses the parallax range [minD, maxD] to obtain the parallax of the subsequent feature point, furthermore, the parallax of the subject or the distance between the subject and the stereo camera, so that the amount of calculation performed by the image fair- have.

 4 is an exemplary diagram for explaining an operation in which an image pair processing apparatus according to an embodiment determines feature points in a target area.

Referring to FIG. 4, feature points extracted from the target regions 410 and 420 by the image pair processing apparatus are displayed in dots. The image pair processing apparatus can extract characteristic points based on an ORB (Oriented FAST and Rotate BRIEF) method. In addition, the image pair processing apparatus can extract feature points based on BRISK (Binary Robust Invariant Scalable Keypoints) BRISK (Binary Robust Invariant Scalable Keypoints) method, OFAST method, or FAST method.

In order to determine the distance between the subject and the stereo camera, the image-pair processing apparatus can calculate only the parallax of the extracted feature points instead of obtaining the parallax of the entire pixels in the target area. Therefore, the time or calculation amount required for the image pair processing apparatus to determine the distance between the subject and the stereo camera can be reduced.

The image pair processing apparatus according to an exemplary embodiment may connect extracted feature points within a target area to generate a link graph for each target area of the frame image. The image pair processing device can measure the horizontal distance, the vertical distance and the Euclidean distance between the feature points, and then connect the two feature points with the measured distance closest to each other. More specifically, (1) for feature point p, if the horizontal distance of feature point q and feature point p is closest, the image pair processing device may connect feature points p and q. (2) For feature point p, if the vertical distance of feature point q and feature point p is closest, the image pair processing device may connect feature points p and q. (3) For feature point p, if the Euclidean distance of feature point q and feature point p is closest, the image pair processing device may connect feature points p and q. The connection graph generated by the image pair processing apparatus is a global graph, in which one feature point is divided into a feature point having a maximum of three different feature points - a minimum horizontal distance, a feature point having a minimum vertical distance, a feature having a minimum Euclidean distance It can be a 3-connected graph connected to points.

An image pair processing apparatus according to an embodiment can generate a minimum tree from each generated connection graph as nodes of each feature point in the target area. Therefore, the minimum tree can be generated for each target area of the frame image. 5 is an exemplary diagram illustrating an operation in which an image pair processing apparatus according to an embodiment generates a minimum tree.

The image pair processing device can determine the weight of each edge of the connection graph as the spatial distance between two feature points connected along the sides. The image pair processing device can generate the minimum tree by concatenating the feature points based on the determined weight. The minimum tree may include, among all sides of the connection graph, sides that minimize the sum of the weights. The minimum tree may be a minimum spanning tree (MST) or a segment tree (ST). Referring to FIG. 5, the minimum tree created by the image pair processing device from the feature points of the target areas 510, 520 is shown. The minimum extension tree is shown in the target area 510, with the minimum pair of trees generated by the image pair processing device from the feature points. The partition tree is shown in the target area 520, with the minimum tree created by the image pair processing device from the feature points.

For example, an image pair processing apparatus can generate a minimum extension tree using a prim algorithm. More specifically, the image pair processing apparatus may select one of the feature points as a root node, and then, among the sides of the feature point selected as the root node, add the least weighted side to the minimum tree. The image pair processing device can identify another feature point connected to the feature point selected as the root node through the side added to the minimum tree. The image pair processing device may select another feature point identified as a leaf node that is a child node of the root node. The image fair processing apparatus can add, to the minimum tree, the side having the smallest weight among the sides of the feature points selected as the leaf nodes (more specifically, the side having the smallest weight among the remaining sides except the side added to the minimum tree) . The image pair processing apparatus can repeatedly perform the above-described operation for the side added with the minimum tree among the sides of the leaf node, thereby generating a minimum extension tree connecting all the feature points starting from the feature point selected as the root node .

The image pair processing apparatus can generate a minimum tree for each target area of each of the frame images included in the image pair. The image pair processing device may generate the first minimum tree from the target area of the first frame image and likewise generate the second minimum tree from the target area of the second frame image. The image pair processing device can accumulate the measured costs at each of the feature points based on the generated first minimum tree or the second minimum tree.

More specifically, the image-pair processing apparatus calculates the feature point of the first frame image and the feature point of the second frame image based on the luminance and parallax of the feature point of the first frame image and the corresponding feature point of the second frame image, Can be determined. The image pair processing apparatus can use the predetermined time difference range when determining the cost. The image pair processing apparatus can determine the cost for each feature point corresponding to each node of the minimum tree.

The image pair processing device may determine the cost of matching the feature point of the first frame image and the feature point of the second frame image based on a BT (Birchfield and Tomasi) cost or a Census (statistical) cost . In determining the BT cost, linear interpolation may be used to reduce the sensitivity due to the image sampling effect. The Census cost can be determined based on the number of pixels having luminance lower than the luminance of the current pixel by comparing the luminance of the current pixel and the luminance of the adjacent pixel adjacent to the current pixel. Thus, the cost of the Census can be robust to illumination. An image pair processing apparatus according to an embodiment can determine the cost of matching the feature point of the first frame image and the feature point of the second frame image by combining the BT cost and the Census cost based on Equation (3).

Referring to Equation (3), C (p) denotes a cost when matching a pixel p (for example, a feature point) of the first frame image with a corresponding pixel of the second frame image. w denotes the weight between the BT cost and the Census cost. C _BT (p) means the BT cost for pixel p, and C _Census (p) means Census cost for pixel p. 6 is a graph showing the results of a comparative experiment for AD, census, and AD + census. Referring to FIG. 6, a comparison experiment result of a middleburry for AD (absolute intensity differences), Census, AD + Census is shown.

The image pair processing apparatus may determine a matching cost vector that represents the cost of matching the feature point of the first frame image and the feature point of the second frame image from C (p). The number of matching cost vectors may be equal to the number of parallaxes included in the parallax range. As described above, since the parallax range is determined to be a relatively small range including the parallax with the smallest luminance difference, the amount of calculation can be reduced as the dimension of the matching cost vector is reduced.

After determining the cost of matching the feature points for each feature point corresponding to each node of the minimum tree, the image fair processing apparatus can accumulate the cost determined for each node along the leaf node at the root node of the minimum tree. The image fair processing apparatus can accumulate the costs of the lower nodes (i.e., subnodes) of each node along the direction from the root node to the leaf node, in each of the nodes of the minimum tree. The image fair processing apparatus can accumulate the cost of an upper node (a node of a node) of each node along a direction from the leaf node to the root node, in each of the nodes of the minimum tree.

The image fair processing apparatus includes a cumulative matching cost calculation unit for calculating a cumulative cost based on a result of accumulating the costs of the lower nodes of each node and the costs determined by the nodes of the minimum tree centered on each node, Can be determined. More specifically, the image pair processing apparatus can determine the cumulative matching cost based on the filtering method of the minimum tree. When the image pair processing apparatus accumulates the costs of the child nodes (i.e., the sub nodes) for each node of the minimum tree along the direction from the root node to the leaf node, the image pair processing apparatus calculates, based on Equation 4, Can be accumulated.

는 픽셀 p(즉, 최소 트리의 특정 노드에 대응하는 특징 포인트)의 변화 후의 누적 비용을 나타내고,

는 픽셀 p의 초기 비용을 의미한다. Ch(p)는 픽셀 p에 대응하는 노드의 모든 서브 노드의 집합을 의미한다. S(p, q)는 픽셀 p 및 서브 노드에 포함된 픽셀 q(즉, 최소 트리의 특정 노드의 하위 노드에 대응하는 특징 포인트)의 유사도를 의미한다. D는 매칭 비용 벡터이고, 매칭 비용 벡터의 차원의 개수와 시차 범위의 시차의 수는 서로 동일할 수 있다. 시차 범위가 휘도 차이를 최소로 하는 시차를 포함하는 상대적으로 작은 범위로 결정되므로, 매칭 비용 벡터의 차원(dimension)이 감소됨에 따라 계산량이 감소될 수 있다. 이미지 페어 처리 장치는 수학식 4에 기초하여, 최소 트리의 특정 노드의 모든 하위 노드를 탐색한 다음, 특정 노드의 누적 매칭 비용을 업데이트할 수 있다.Referring to Equation 4,

Represents the cumulative cost after the change of the pixel p (i. E., The feature point corresponding to a particular node of the minimum tree)

Is the initial cost of pixel p. Ch (p) denotes a set of all the subnodes of the node corresponding to the pixel p. S (p, q) denotes the similarity of the pixel p and the pixel q included in the sub node (that is, the feature point corresponding to the child node of the specific node of the minimum tree). D is a matching cost vector, and the number of dimensions of the matching cost vector and the number of parallaxes of the parallax range may be equal to each other. Since the parallax range is determined to be a relatively small range including the parallax that minimizes the luminance difference, the amount of calculation can be reduced as the dimension of the matching cost vector is reduced. The image fair processing apparatus can search all the lower nodes of the specific node of the minimum tree based on the equation (4), and then update the cumulative matching cost of the specific node.

When the image pair processing apparatus accumulates the cost of an upper node (i.e., a node of a node) for each node of the minimum tree along the direction from the leaf node to the root node, the image pair processing apparatus calculates, Can be accumulated.

는 픽셀 p에 대응하는 노드의 파더 노드를 매칭할때의 비용을 의미한다. 수학식 5를 참고하면, 최종적으로 계산되는 비용

은 픽셀 p에 대응하는 노드의 파더 노드에 의하여 결정됨을 알 수 있다.In Equation (5), Pr (p) denotes a node of a node corresponding to a pixel p (i.e., a feature point corresponding to a specific node of the minimum tree) The degree of similarity between the corresponding node and its corresponding node,

Represents the cost when matching the node of the node corresponding to the pixel p. Referring to Equation (5), the finally calculated cost

Is determined by the node of the node corresponding to pixel p.

S (p, q) in Equation 4 and S (Pr (p), p) in Equation 5, which are the similarities between two feature points, can be determined based on Equation (6).

In Equation 6, I (p) and I (q) are each pixel p, meaning the intensity value of q, and x _p, and x _q are the horizontal coordinates of each pixel p, q (x coordinate), y _p And y _q denote the vertical coordinates (y-axis coordinate) of the pixels p and q, respectively. σ _s and σ _r are fixed parameters and can be adjusted experimentally.

The image pair processing apparatus can determine the parallax, depth, or depth information of feature points corresponding to each of the nodes of the minimum tree based on a parallax that minimizes the cumulative matching cost. For example, the image pair processing apparatus can determine the parallax of feature points using the winner-takes-all method. The image pair processing apparatus can determine the parallax of feature points based on Equation (7).

Referring to Equation (7), f _p is the parallax of a pixel p (i.e., a feature point corresponding to a specific node of the minimum tree for the target area of the first frame image), C '(p, d) The pixel p of the first frame image is matched. D means the time difference range. The image pair processing device can determine the distance between the subject and the stereo camera based on the parallax of the determined feature point. After determining the distance between the subject and the stereo camera, the image pair processing device can perform alarm processing or manipulation processing. For example, when the subject is any one of a vehicle, a road sign, a passenger, an obstacle, and a landscape, the operational process may include at least one of braking and redirecting of an object (e.g., .

FIG. 7 is a diagram for explaining an operation of determining an image pair processing apparatus according to an embodiment, the distance between a subject and a stereo camera included in an image pair. FIG. A computer-readable recording medium on which a program for executing an image pair processing method according to an embodiment is recorded can be provided. The program may include at least one of an application program storing an image pair processing method, a device driver, a firmware, a middleware, a dynamic link library (DLL), and an applet. According to one embodiment, the image pair processing apparatus includes a processor, and the processor can perform the image pair processing method by reading the recording medium on which the image pair processing method is recorded.

Referring to FIG. 7, in step 710, an image pair processing apparatus according to an embodiment may generate a target area in a frame image. The target area may be a part of a frame image, and may include a subject photographed by a stereo camera that has generated the frame image.

When the image pair processing apparatus receives a pair of a plurality of frame images generated from a plurality of image sensors included in a stereo camera, the image pair processing apparatus generates a target area including a subject in each of the plurality of frame images . When the stereo camera includes two image sensors, the image pair processing apparatus can receive the pair of the first frame image and the second frame image. The image pair processing apparatus can generate the target area including the subject in each of the first frame image and the second frame image of the image pair.

Referring to FIG. 7, in step 720, an image pair processing apparatus according to an embodiment may determine a parallax range of a target area. In other words, the image-pair processing apparatus can determine the range in which the parallax of the subject included in the target area is expected to be included. The image pair processing apparatus can identify a corresponding region having the same position, shape and size as the target region in the target region extracted from any one of the plurality of frame images and the other frame images. The image pair processing apparatus can calculate the luminance difference of the target area and the corresponding area.

The image pair processing apparatus can calculate the luminance difference of the target area and the corresponding area in the plurality of corresponding areas. More specifically, the image pair processing apparatus can calculate the luminance difference of the target area and the corresponding area while moving the corresponding area in parallel along the horizontal direction at the same height as the target area. In other words, the y coordinate of the corresponding area is fixed, and only the x coordinate can be changed.

The parallax range can be determined so as to include the parallel movement amount (i.e., parallax) of the corresponding area that minimizes the luminance difference. For example, the image pair processing apparatus can apply the parallel shift amount of the corresponding region that minimizes the luminance difference to Equations (1) and (2) to determine the parallax range. Therefore, the parallax range can be determined as a part of the whole range in which the corresponding region can move in parallel.

Referring to FIG. 7, in step 730, an image pair processing apparatus according to an embodiment may extract feature points in a target area. The image pair processing device may extract feature points in a target area of each of a plurality of frame images of the image pair.

Referring to FIG. 7, in step 740, the image pair processing apparatus according to an embodiment may connect the extracted feature points to generate a connection graph. The nodes of the connection graph are feature points, and the nodes can be connected based on horizontal distance, vertical distance or Euclidean distance between feature points. The image pair processing apparatus can connect any feature point to another feature point whose horizontal distance is closest. The image pair processing apparatus can connect a certain feature point with another feature point whose vertical distance is closest. The image pair processing device can connect a certain feature point to another feature point nearest the Euclidean distance. The connection graph can be generated for each target area of each of a plurality of frame images.

Referring to FIG. 7, in step 750, the image pair processing apparatus according to an embodiment may generate a minimum tree from the generated connection graph. The minimum tree may be generated for each target area of each of the plurality of frame images corresponding to the connection graph, and all feature points included in the target area may be nodes. The image pair processing device can determine the weight of each of the sides of the connection graph based on the spatial distance between two feature points connected along the sides. The image pair processing apparatus can select the side that minimizes the sum of the weights and generate the minimum tree based on the selected side.

Referring to FIG. 7, in step 760, the image pair processing apparatus according to an embodiment may determine the cost of matching each of the nodes of the minimum tree. In other words, since each of the nodes corresponds to a feature point, the cost of matching feature points in different frame images can be determined. The cost may be determined according to the luminance of the target area and the disparity range determined in step 720. [ The image fair processing apparatus can determine the cost of matching each of the nodes of the minimum tree based on Equation (3). Step 720 may be performed concurrently with at least one of steps 730 through 750. [ In addition, step 720 may be performed between steps 730 and 750. [

Referring to FIG. 7, at step 770, an image pair processing apparatus according to an embodiment may accumulate the determined cost in each of the plurality of nodes of the minimum tree along the branches of the minimum tree. The image fair processing apparatus can search the minimum tree along the upper direction or the lower direction of the specific node for a specific node of the minimum tree. The image fair processing apparatus can accumulate the determined cost in each of the plurality of nodes by combining the cost of matching the detected node in each direction with the cost of matching the specific node. For example, the image pair processing apparatus may accumulate the determined cost in each of the plurality of nodes along the branch of the minimum tree based on (4) or (5).

Referring to FIG. 7, in step 780, the image pair processing apparatus according to one embodiment can determine the parallax of the feature point based on the accumulated cost. More specifically, the image pair processing apparatus accumulates the parallax of a feature point corresponding to a specific node of a minimum tree, the cost when matching a specific node with another node connected through a minimum tree to the cost of matching a specific node, Can be determined based on a result.

Referring to FIG. 7, at a point 790, an image pair processing device according to an embodiment can determine the distance between the subject and the stereo camera based on the parallax of the determined feature point. Taken together, in determining the distance between the subject and the stereo camera, the image-pair processing apparatus determines only the parallax of some pixels (feature points) of the target area, instead of determining the parallax of all the pixels of the target area containing the subject , The amount of computation or time required to determine the distance between the subject and the stereo camera may be reduced. Further, the image-pair processing apparatus performs the operation of determining the parallax of the feature point within the limited parallax range without measuring the parallax of the feature point in all possible parallaxes, so that the amount of calculation or time required to determine the parallax of the feature point is reduced . The image pair processing apparatus can perform alarm processing or operational processing based on the distance between the determined subject and the stereo camera.

Hereinafter, an experimental result of measuring the distance of 280 subjects included in a public data set KITTI including a plurality of image pairs according to a method of accumulating costs along a minimum tree will be described in accordance with an embodiment of the present invention . Subjects include vehicles, road signs, and passers-by. Table 1 shows the accuracy and the time when the distance to the subject is determined based on the result of accumulating the cost when the image pair processing apparatus matches the feature point using the minimum extension tree or the segmentation tree without accumulating the cost Together with the accuracy and time when the distance to the subject is determined.

Dataset Way accuracy time KITTI
(Including 280 subjects) Match frame images without accumulating costs 80.41% 3.7ms Matching frame images using minimum extension tree (MST) 90.25% 4.53ms Matching frame images using segment tree (ST) 90.39% 4.65ms

Referring to Table 1, the accuracy of the distance between the subject and the stereo camera measured by the image pair processing apparatus according to an embodiment is about 90%, and the distance between the subject and the stereo camera is measured by matching the frame image without accumulating the cost The accuracy is improved by about 10%.

Furthermore, the image-pair processing apparatus according to an embodiment can track the position of a subject commonly included in a plurality of image pairs, with respect to a plurality of image pairs sequentially obtained with time. Fig. 8 is a flowchart for explaining an operation of an image-pair processing apparatus according to an embodiment for tracking the position of an object commonly included in a plurality of image pairs.

Referring to FIG. 8, in step 810, the image pair processing apparatus according to an embodiment may generate a target area in the last inputted current frame image. The operation of the image pair processing device to create the target area may be similar to that described in step 710. [ The target area may include an object to be tracked by the image pair processing device.

Referring to FIG. 8, in step 820, the image pair processing apparatus according to an embodiment can extract the feature value of the generated target area. In step 830, the image pair processing device may filter the feature values of the target area of the current frame image. In step 840, the image pair processing device may interpolate the filtered feature value to generate a feature value plane corresponding to the current frame image.

In step 850, the image pair processing device may compare the generated feature value plane and the feature value plane model generated from the frame image obtained earlier than the current frame image. The feature value plane model may be generated by being updated or trained by one or more frame images obtained prior to the current frame image. More specifically, the image pair processing apparatus can fit the generated feature value plane to the feature value plane model. The image pair processing apparatus can calculate the response value when the feature value plane is fitted to the feature value plane model.

In step 860, the image pair processing device may determine the position of the subject within the current frame image based on the comparison of the feature value plane and the feature value plane model. More specifically, the image pair processing apparatus can determine the position at which the response value is maximized as the position of the subject. In step 870, the image pair processing device may update the feature value plane model based on the position of the subject within the current frame image.

The image pair processing device can determine the position of the subject at the subpixel level. An image pair processing device can provide sub-pixel level accuracy using a planar interpolation fitting method.

에 기초하여 결정될 수 있다. 그래프(900)를 참고하면, 응답값의 최대값은 현재 프레임 이미지에서 피사체의 위치에 대응할 수 있다. 응답값을 최대로 하는 (x*, y*)는 응답함수 R(x,y)의 편미분 함수

에 기초하여 수학식 8과 같이 결정될 수 있다.9 is a graph 900 showing a distribution of response values calculated by fitting an image plane processing apparatus according to an embodiment to a feature value plane model. The response value is the response function

. ≪ / RTI > Referring to the graph 900, the maximum value of the response value may correspond to the position of the subject in the current frame image. (X *, y *) which maximizes the response value is the partial derivative of the response function R (x, y)

(8) < / RTI >

The six parameters a through f of the response function R (x, y) can be determined based on an overdetermined equation. More specifically, the image pair processing apparatus can obtain six equations using the response values of six points near (x *, y *) at which the response value becomes the maximum. The image pair processing apparatus can determine the parameters a to f by concatenating the obtained equations based on the substitution method or the erase method.

Hereinafter, an experimental result in which an image pair processing apparatus according to an embodiment determines the position of a subject from nine video images selected from a public data set (OOTB) will be described. The nine selected video images include FaceOcc1, Coke, David, Bolt, Car4, Suv, Sylvester, Walking2 and Singer2. The accuracy with which the image pair processing apparatus tracks the subject is shown in Table 2.

Precise configuration FaceOcc1 Coke David Bolt Car4 Suv Sylvester Walking2 Singer2 KCF 0.730 0.838 1.0 0.989 0.950 0.979 0.843 0.440 0.945 Subpixel KCF 0.754 0.873 1.0 0.997 0.953 0.980 0.851 0.438 0.962

Referring to Table 2, it can be seen that the accuracy (subpixel KCF) that the image pair processing apparatus according to one embodiment tracks the position of the subject is improved over that of the conventional method of tracking the subject position.

Taken together, since the image pair processing apparatus according to the embodiment extracts feature points from a target area smaller than the received frame image, the time or amount of calculation for extracting feature points can be reduced. Further, since the image pair processing apparatus performs operations such as matching of feature points, parallax measurement, and the like with respect to feature points that are part of the target area, the time or calculation amount consumed in processing the frame images can be reduced. The image fair processing apparatus can reduce the calculation amount when determining the parallax of feature points by filtering and removing the cumulative matching cost when determining the minimum cumulative matching cost for the nodes of the minimum tree.

In addition, since the plurality of extracted feature points include the characteristics of the subject, the accuracy of the distance of the subject and the stereo camera determined based on the feature point can be improved. Therefore, when the distance between the subject and the stereo camera is measured with the same accuracy, the image-pair processing apparatus according to one embodiment can improve the speed of processing an image pair by reducing the amount of calculation of the entire process of processing the image pair .

In addition, the image pair processing apparatus can reduce the size of the parallax range used when matching the feature points of the target area by determining the parallax range for the target area. More specifically, since the number of matching cost vectors calculated by the image pair processing apparatus is reduced by the number of parallaxes in the parallax range, the operation of determining the cost when matching the feature points and the amount of calculation of the operation of accumulating the determined cost are reduced .

Additionally, an image pair processing apparatus according to an embodiment may generate a connection graph that nodes a plurality of feature points based on a plurality of feature points in a target area. Further, the image pair processing apparatus can reduce the number of sides included in the connection graph while maintaining all the feature points as nodes by generating a minimum tree from the connection graph.

In addition, the image-pair processing apparatus according to an exemplary embodiment extracts a feature value of a target area of a current frame image, and then generates a feature value plane for the current frame image using interpolation for the extracted feature value. The image pair processing device can determine the position of the subject in the current frame image by comparing the feature value plane model generated from the frame image acquired before the current frame image with the generated feature value plane. Thus, the image-pair processing apparatus can more accurately determine the position of the subject in the current frame image.

The embodiments described above may be implemented in hardware components, software components, and / or a combination of hardware components and software components. For example, the devices, methods, and components described in the embodiments may be implemented within a computer system, such as, for example, a processor, a controller, an arithmetic logic unit (ALU), a digital signal processor, such as an array, a programmable logic unit (PLU), a microprocessor, or any other device capable of executing and responding to instructions. The processing device may execute an operating system (OS) and one or more software applications running on the operating system. The processing device may also access, store, manipulate, process, and generate data in response to execution of the software. For ease of understanding, the processing apparatus may be described as being used singly, but those skilled in the art will recognize that the processing apparatus may have a plurality of processing elements and / As shown in FIG. For example, the processing unit may comprise a plurality of processors or one processor and one controller. Other processing configurations are also possible, such as a parallel processor.

The software may include a computer program, code, instructions, or a combination of one or more of the foregoing, and may be configured to configure the processing device to operate as desired or to process it collectively or collectively Device can be commanded. The software and / or data may be in the form of any type of machine, component, physical device, virtual equipment, computer storage media, or device , Or may be permanently or temporarily embodied in a transmitted signal wave. The software may be distributed over a networked computer system and stored or executed in a distributed manner. The software and data may be stored on one or more computer readable recording media.

The method according to an embodiment may be implemented in the form of a program command that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions to be recorded on the medium may be those specially designed and configured for the embodiments or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of program instructions include machine language code such as those produced by a compiler, as well as high-level language code that can be executed by a computer using an interpreter or the like. The hardware devices described above may be configured to operate as one or more software modules to perform the operations of the embodiments, and vice versa.

Although the embodiments have been described with reference to the drawings, various technical modifications and variations may be applied to those skilled in the art. For example, it is to be understood that the techniques described may be performed in a different order than the described methods, and / or that components of the described systems, structures, devices, circuits, Lt; / RTI > or equivalents, even if it is replaced or replaced.

101: Stereo camera
102: target area generator
103: Feature point extractor
104: Matching cost meter
105: Features Point difference calculator
106: Subject distance determiner
107: Feature point connector
108: Minimum Tree Generator
109:
110: subject tracker

Claims (15)

Generating, in each of a first frame image and a second frame image of an image pair obtained from a stereo camera that has photographed a subject, a target area including the subject;
Extracting feature points in the target area;
Calculating a parallax of the feature point by matching the feature point extracted from the first frame image and the feature point extracted from the second frame image; And
Determining a distance between the subject and the stereo camera based on the parallax of the feature point
/ RTI > The method according to claim 1,
Wherein the calculating step comprises:
Connecting a feature point of the first frame image based on a horizontal distance, a vertical distance or an Euclidean distance between the feature points of the first frame image, ≪ / RTI >
A second tree that connects feature points of the second frame image based on a horizontal distance, a vertical distance, or an Euclidean distance between the feature points of the second frame image, ≪ / RTI > And
Matching the nodes of the first tree and the nodes of the second tree to calculate the parallax of the feature point of the first frame image and the feature point of the second frame image
/ RTI > 3. The method of claim 2,
The matching step comprises:
Accumulating the costs of matching the nodes of the first tree and the nodes of the second tree along the branches of the nodes of the first tree; And
Determining a parallax of a feature point of the first frame image and a feature point of the second frame image based on the accumulated cost
Lt; / RTI >
The above-
And the luminance and parallax of the nodes of the first tree and the nodes of the second tree that are the objects of matching. The method according to claim 1,
Determining a parallax range associated with the subject based on a luminance difference between a corresponding region of a second frame image determined according to a target region of the first frame image and a position of the target region
Further comprising the steps of: 5. The method of claim 4,
Wherein the step of calculating the parallax of the feature point comprises:
Wherein the feature points extracted from the first frame image and the feature points extracted from the second frame image are matched within the determined parallax range. 5. The method of claim 4,
Wherein the step of determining the parallax ranges comprises:
Moving a corresponding region of the second frame image in parallel; And
Comparing the luminance of the corresponding region of the parallel moved and the target region of the first frame image
/ RTI > The method according to claim 1,
Extracting a feature value of the target area;
Generating a feature value plane of the image pair based on the extracted feature value;
Comparing a feature value plane model generated from a feature value plane of an image pair obtained before the image pair with the feature value plane; And
Determining a position of the subject in the image pair based on a result of comparing the feature value plane model and the feature value plane
Further comprising the steps of: 8. The method of claim 7,
Changing the feature value plane model based on the determined position of the subject
Further comprising the steps of: A memory for storing an image pair photographed by a subject; And
The processor for processing the image pair
Lt; / RTI >
The processor comprising:
In each of a first frame image and a second frame image of the image pair, a target area including the subject is generated,
Extracting feature points in the target area,
Calculating a parallax of the feature point by matching the feature point extracted from the first frame image and the feature point extracted from the second frame image,
And determines a distance between the subject and the stereo camera that has photographed the subject based on the parallax of the feature point. 10. The method of claim 9,
The processor comprising:
Based on a cost of matching a first tree having characteristic points of the first frame image as nodes and a second tree having characteristic points of the second frame image as nodes, And calculates the parallax of the feature point of the second frame image. 11. The method of claim 10,
The processor comprising:
And determines the cost using the similarity determined based on the luminance and the parallax of the feature point corresponding to the node of the first tree and the feature point corresponding to the node of the second tree. 11. The method of claim 10,
Wherein each of the first tree and the second tree comprises:
Wherein the feature points of the first frame image having the smallest spatial distance and the feature points of the second frame image having the smallest spatial distance are connected. 10. The method of claim 9,
The processor comprising:
And determines a parallax range associated with the subject based on a luminance difference between a corresponding region of the second frame image determined according to the target region of the first frame image and the position of the target region. 14. The method of claim 13,
The processor comprising:
And compares feature points extracted from the first frame image and feature points extracted from the second frame image within the determined parallax range. 10. The method of claim 9,
The processor comprising:
Extracting a feature value of the target area,
Generating a feature value plane of the image pair based on the extracted feature value,
Comparing the feature value plane model generated from the feature value plane of the image pair obtained before the image pair with the feature value plane,
And determines the position of the subject in the image pair based on a result of comparing the feature value plane model and the feature value plane.

Images