Method for determining ground line

A method of determining a ground line from an input image. The method includes determining a plurality of ground line candidates from the image, determining a certain band a central-line of which is a boundary between a G region and other regions in a Ground Building Sky (GBS) map of the image, and determining the ground line of the image by selecting a ground line candidate, among the plurality of ground line candidates, having the greatest extent crossing the certain band.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of Russian Patent Application No. 2008132273, filed on Jul. 17, 2008 in the Russian Patent Office and Korean Patent Application No. 10-2008-0105977, filed on Oct. 28, 2008, in the Korean Intellectual Property Office, the entire disclosures of which are incorporated herein by reference.

BACKGROUND

One or more embodiments relate to an image processing method, and more particularly, to determining a ground line that is a boundary line between a building region and a ground region in an image.

2. Description of the Related Art

Currently, research is being conducted regarding three-dimensional (3D) image modeling from a color image. One advantageous technique being researched is an image processing technique that performs segmenting a ground region, a building region, and sky region from the image and determines a ground line that is a boundary line between a building region and a ground region.

If the ground line can be determined, 3D image modeling is possible by cutting an image around the ground line and setting up the same as a vertical structure. The image modeling is applicable to a Motion Pictures Experts Group 4 (MPEG-4) encoding method based on objects. Specifically, with respect to a method for restoring a 3D image from a 2D image of a city where artificial structures exist, the method for determining the ground line may significantly affect efficiency of image processing.

SUMMARY

An aspect of one or more embodiments, contrived for 3D image modeling, provides a method and apparatus for determining a ground line between a building and ground in an image.

Another aspect of one or more embodiments also provides a method and apparatus for automatically determining a ground line in an inputted 2D image.

Another aspect of one or more embodiments also provides a method and apparatus for effectively determining a ground line in an image where a plurality of buildings exist.

According to an aspect of one or more embodiments, there is provided a method of determining a ground line of an image, including determining a plurality of ground line candidates from the image, determining a certain band having a central-line being a boundary between a ground (G) region and other regions in a Ground Building Sky (GBS) map of the image, and determining the ground line of the image by selecting a ground line candidate, among the plurality of ground line candidates, having the greatest number of point lying within the certain band.

In an aspect of one or more embodiments, the method further includes detecting a plurality of horizontal straight lines belonging to a B region of the image, and determining the plurality of ground line candidates using the plurality of horizontal straight lines.

In an aspect of one or more embodiments, the method of detecting the plurality of horizontal straight lines belonging to a B region of the image includes extracting a plurality of straight lines from the image, detecting a plurality of horizontal straight lines from among the plurality of straight lines, and selecting the plurality of horizontal straight lines belonging to the B region from among the plurality of horizontal straight lines.

In an aspect of one or more embodiments, the method of detecting a plurality of horizontal straight lines from among the plurality of straight lines includes comparing the B region in the GBS map of the image with the plurality of horizontal straight lines, and selecting the plurality of horizontal straight lines belonging to the B region, based on the comparing.

In an aspect of one or more embodiments, the method further includes clustering the plurality of horizontal straight lines into a plurality of groups, and the determining of the plurality of ground line candidates may be based on the clustered plurality of horizontal straight lines.

In an aspect of one or more embodiments, the method further includes determining a vanishing point of each of the plurality of groups, determining a vertical boundary line between the plurality of groups, and detecting a straight line that passes through a plurality of points of the vertical boundary line and the vanishing point of each of the plurality of groups.

In an aspect of one or more embodiments, the determining of the ground line of the image includes determining a certain band having a central-line of which is a boundary between a G region and other regions in the GBS map of the image, and determining the ground line of the image depending on to what degree each of the plurality of ground line candidates is within the certain band.

According to another aspect of one or more embodiments, there is provided a method of determining a ground line, including extracting a plurality of straight lines from an image, determining a plurality of ground line candidates using a vanishing point of the plurality of straight lines, and determining a ground line of the image from among the plurality of ground lines using a GBS map of the image.

DETAILED DESCRIPTION

FIG. 1illustrates a flowchart of a method for determining a ground line of an image according to an embodiment of the present invention;

In operation110, an image is inputted. According to embodiments of the present invention, the image is an image file comprised of RGB data. A file format of the color image may be in a variety of types, such as a bitmap (.bmp file), Joint Photographic Experts Group (.jpeg, .jpg files), and raw file formats. When the file format is in a data-compressed format, decompression may be performed before a start of the image processing.

According to one or more embodiments, accuracy and/or efficiency of image processing increases through a variety of pre-processing of the input image. For example, a value (or a brightness) or a contrast of the input image is adjusted, and the adjusted resulting image can be an input image for the image processing. Also, the pre-processing may include a variety of filter mask processes.

In operation120, a Ground Building Sky (GBS) map of the input image is generated. The GBS map shows an image that is simply segmented into substantial portions, namely, a ground region, building region, and sky region. To generate the GBS map, information, such as a color, location, texture, and the like, is learned from a plurality of images where the above mentioned regions exist. Then, when a new image is given, the new image is segmented into each region using the learned information, and thereby can generate a GBS map of the new image.

In operation130, a plurality of horizontal straight lines belonging to the building region are extracted. According to embodiments of the present invention, a plurality of straight lines are extracted from an input image using a Sobel Edge Detector. A plurality of horizontal straight lines are extracted from among the plurality of straight lines, and non-horizontal straight lines are filtered out. Also, the GBS map of the input image and the plurality of horizontal straight lines are compared. A plurality of horizontal straight lines corresponding to a G region and S region of the GBS map from among the plurality of horizontal straight lines are filtered out, and thus the plurality of horizontal straight lines belonging to the B region are extracted.

In operation140, the plurality of horizontal straight lines belonging to the B region are clustered into a plurality of groups. According to embodiments of the present invention, x coordinates of the plurality of horizontal straight lines belonging to the B region are clustered into a middle-phase group using a mean shift algorithm. Then, an outlier of each of the middle-phase groups is eliminated using a Random Sample Consensus (RANSAC) algorithm. A main direction of each of the middle-phase groups is calculated and another clustering using the mean shift algorithm is performed, and thus, a plurality of groups in a bigger unit are generated by merging similar main directions of the middle-phase groups.

In operation150, a vanishing point of each of the plurality of groups is determined. A plurality of vanishing points is extracted from a plurality of straight lines in the plurality of groups. In this instance, a vanishing point of an outlier which is not eliminated from the plurality of groups may be extracted. The vanishing point of the outlier is eliminated and the plurality of vanishing points of an inlier are averaged, and thus a number of final vanishing points are extracted. According to one or more embodiments, the number of final vanishing points is equal to or less than a number of the groups, because although one vanishing point is extracted in each group, a group which may be comprised of only parallel straight lines would not have a vanishing point.

In operation160, a vertical boundary line between the plurality of groups is determined. According to one or more embodiments, 10% of a portion of edges of each of the plurality of groups are selected, and the longest vertical straight line within an edge region between neighboring groups is determined as the boundary line between the plurality of groups. The vertical boundary line is a point where the ground line curves.

In operation170, straight lines that pass through a plurality of points of the vertical boundary line and a vanishing point of each of the plurality of groups are determined as a plurality of ground line candidates. For example, a straight line that passes through each pixel of the vertical boundary line and a vanishing point of each of the plurality of groups is determined as a ground line candidate. The ground line candidate in a group with no vanishing point becomes a straight line parallel to a horizon.

In operation180, a certain band having a central-line being a boundary between a G region and other regions is determined. According to one or more embodiments, pixels that are added, either in a positive or negative y coordinate direction to each pixel of the vertical boundary line are determined as the certain band.

In operation190, a ground line of the image is determined depending on to what degree each of the plurality of ground line candidates is within the certain band. The ground line candidates are compared with the certain band and then a candidate which is most within the certain band is determined as a ground line of the image from among the plurality of ground line candidates. According to an embodiment of the present invention, a number of pixels, of each of the plurality of ground line candidates, that cross the certain band is calculated, and a ground line candidate that has the greatest number of pixels that cross the certain band, is selected as the ground line of the image.

FIG. 2illustrates an image inputted according to an embodiment of the present invention. A region210corresponds to a Sky (S) region, a region220corresponds to a Building (B) region, and a region230corresponds to a Ground (G) region. Each of the regions has a boundary between the regions. A car240in the input image is located in a boundary between the B region220and the G region230. Therefore, the car240and the like is a factor that causes an error in a ground line of a GBS map through simple image segmentation.

FIG. 3illustrates an example of a GBS map image extracted from an input image, for example, the input image ofFIG. 2according to an embodiment of the present invention. A region310corresponds to an S region, a region320corresponds to a B region, a region330corresponds to a G region. A boundary340is a boundary between the G region and other regions. The boundary340is not a straight line in the example image. According to an embodiment, a certain band having a central-line of which is the boundary340is determined, a ground line of the input image is determined depending on to what degree each of the plurality of ground line candidates is within the certain band.

FIG. 4illustrates a flowchart of a process of extracting a plurality of horizontal straight lines belonging to a B region from among a plurality of horizontal straight lines, according to an embodiment of the present invention.

In operation410, a plurality of straight lines are extracted from an input image. According to an embodiment, the plurality straight lines may be extracted using a Sobel Edge Detector. An operator mask for the x and y axes of the Sobel Edge Detector is shown below, for example, in Equation 1.

Here, the Gx indicates a Sobel X gradient map, Gy indicates a Sobel Y gradient map. The A indicates a data of the image. The matrix [1, 0, −1; 2, 0, −2; 1, 0, −1] corresponds to a mask of an X axis, and the matrix [1, 2, 1; 0, 0, 0; −1, −2, −1] corresponds to a mask of a Y axis.

In operation420, a plurality of horizontal straight lines are extracted from among the plurality of straight lines. Following operation410, non-horizontal straight lines are filtered out from among the extracted plurality of straight lines, and thus the plurality of horizontal straight lines are extracted.

According to one or more embodiments, in operations410and420, a Sobel operator of a Y axis may be applied to the image to generate a Sobel gradient image, and thus a plurality of horizontal edges are extracted and a plurality of straight lines are extracted from the horizontal edges.

In operation430, a plurality of horizontal straight lines belonging to a B region are extracted from among the plurality of horizontal straight lines. For example, a GBS map ofFIG. 3is compared with the plurality of horizontal straight lines. Portions corresponding to a G region and B region of the GBS map are filtered out from the plurality of horizontal straight lines. Therefore, only portions corresponding to the B region of the GBS map remain, and thus the plurality of horizontal straight lines belonging to the B region are extracted.

FIG. 5illustrates an example image of a plurality of horizontal straight lines extracted from an image, for example, the image ofFIG. 2according to an embodiment of the present invention. A straight line510and a straight line520are horizontal straight lines belonging to a B region. However, the straight line510and the520are respectively heading towards different vanishing points. Although the straight line530is a straight line, the straight line530is extracted not from the B region, but from tree lining a street in the image ofFIG. 2. A straight line540and a straight line550are straight lines extracted from a traffic lane. The straight lines530,540and550may cause an error during an image processing which determines a ground line.

FIG. 6illustrates an example image of a plurality of horizontal straight lines belonging to a B region extracted from an image, for example, the image ofFIG. 5, according to an embodiment of the present invention. For example, the GBS map ofFIG. 3and the image ofFIG. 5are compared in operation430ofFIG. 4. Portions corresponding to the regions310and330ofFIG. 3are filtered out from the image ofFIG. 5. Thus, only a portion corresponding to the region320remain inFIG. 6. Thus, the straight lines540and550corresponding to the regions310and330from the straight lines510to550inFIG. 5are eliminated and only the straight lines510,520, and530respectively remain as straight lines610,620, and630inFIG. 6.

FIG. 7illustrates a flowchart of a process of clustering the plurality of horizontal straight lines belonging to the B region of an image, for example, the image ofFIG. 6, into a plurality of groups according to an embodiment of the present invention.

In operation710, x coordinates of the plurality of straight lines belonging to the B region are clustered into middle-phase groups using a mean shift algorithm (MSA). The MSA, which is a method for searching a gradient in a probability distribution of a feature value using a repeated performance, statistically effectively finds a peak (or a mode).

In operation720, an outlier of each of the middle-phase groups is eliminated. According to an embodiment, the outlier is eliminated through a Random Sample Consensus (RANSAC) algorithm.

In operation730, a main direction of each middle-phase is calculated. A vector calculation for a plurality of straight lines in each group is performed, so that the main direction of the middle-phase is calculated.

In operation740, middle-phase groups having similar main directions are merged, thereby generating a plurality of groups. If another clustering using the MSA with the main direction calculated in operation730is performed, the plurality of groups in a bigger unit are generated by merging the middle-phase groups with similar main directions.

FIG. 8illustrates an example of a plurality of groups clustered from an image, for example, the image ofFIG. 6, according to an embodiment of the present invention. A cluster810, cluster820, cluster821, cluster822, cluster823, cluster824, cluster831, and cluster832are groups of horizontal straight lines which have the same vanishing point. According to an embodiment of the present invention, several clusters with similar main directions can be merged into another single cluster. Since the clusters821to824have main directions similar to each other, they may be merged into the cluster820. In the same manner, the clusters831and832may be merged into the cluster830. Thus, the plurality of groups, the cluster810, cluster820, and cluster830exist in the example image.

FIG. 9Aillustrates an image of a vanishing point of each of the plurality of groups in an image, for example, the image ofFIG. 8, according to an embodiment of the present invention. An image910shows a process of obtaining a vanishing point. Vanishing points914,915, and916are extracted from the plurality of straight lines in the cluster820ofFIG. 8. Also, vanishing points917,918, and919are extracted from the plurality of straight lines in the cluster830. The vanishing points912and913are vanishing points of outliers which were not eliminated from the cluster. Therefore, the vanishing points912and913of the outliers are eliminated. A vanishing point of an inlier is used for extracting a final vanishing point. Also, since the plurality of straight lines in the cluster810ofFIG. 8are parallel, there is no vanishing point for that cluster. As shown inFIG. 9A, the vanishing points912,913,914,915,916,917,918, and919, may all lie along the same line911.

FIG. 9Billustrates an image of a final vanishing point of each of the plurality of groups in an image ofFIG. 8according to an example embodiment of the present invention. The vanishing points912and913of an outlier inFIG. 9Aare eliminated. A vanishing point922is extracted by averaging the vanishing points914,915, and916inFIG. 9A. A vanishing point923is an average of the vanishing points917,918, and919. Thus, the final vanishing points of the sample image are the vanishing points922and923. As shown inFIG. 9B, the final vanishing points may lie along the same line921.

FIG. 10Aillustrates an image of selected edges of a plurality of groups to determine a vertical boundary line between the plurality of groups according to an embodiment of the present invention. Clusters1011and1012are in the sample image. Since a plurality of straight lines in the cluster1011are parallel with each other, there is a no vanishing point. A plurality of straight lines in the cluster forms a single vanishing point in a left side of the cluster1012.

In an image1010, 10% of a portion of edges of each cluster are selected. A straight line1013and a straight line1014respectively indicate a straight line marking the left 10% edge and a straight line marking the right 10% edge of the cluster1011. Also, a straight line1015and a straight line1016respectively indicate a straight line marking the left 10% edge and a straight line marking the right 10% edge of the cluster1012. According to one or more embodiments, the 10% edge may be replaced with another value.

FIG. 10Billustrates an image of a region between the clusters1011and1012(FIG. 10A) selected to determine a vertical boundary line between the plurality of groups according to an embodiment of the present invention. In an image1020, a region1021between the clusters1014and1015inFIG. 1A, is selected. Each of the clusters1011and1012(FIG. 10A) has a ground line and a portion where the ground line curve is included somewhere within the region1021.

FIG. 10Cillustrates a sample image of a result of determining a vertical boundary line between a plurality of groups according to an embodiment of the present invention.

In an image1030, a boundary line1031corresponds to a vertical boundary line, determined in operation160ofFIG. 1, between the plurality of groups. According to an embodiment, the boundary line1031is the longest straight line from among vertical straight lines in the region1021ofFIG. 10B.

FIG. 11illustrates an example of a plurality of ground line candidates of an image, for example, the image ofFIG. 10, determined in operation170ofFIG. 1, according to an embodiment of the present invention. A boundary line1110corresponds to a boundary line1031ofFIG. 10. A ground line candidate1131which passes through a point1111in the boundary line1110and the clusters1011and1012ofFIG. 10is determined. Since there is no vanishing point of the cluster1011, to the left of point1111the ground line candidate1131is horizontal and to the right of point1111the ground line candidate slopes in a direction heading toward a vanishing point1120of the cluster1012. Also, ground line candidates1132,1133,1134, and1135are determined respectively for points1112,1113,1114, and1115in the boundary line1110.

FIG. 12illustrates an image of determining a certain band having a central-line of which is a boundary between a G region and other regions according to an embodiment of the present invention. A certain band1210having a central-line of which, for example, is a boundary340ofFIG. 3, is determined. According to an embodiment, a predetermined number of pixels added, either in a positive or negative y coordinate direction, to each pixel of the boundary340are determined as the certain band1210.

FIG. 13illustrates an image of a result of determining a ground line from an image, for example, the image ofFIG. 10, according to an embodiment of the present invention. A ground line1310is a ground line of the sample image ofFIG. 10. The ground line candidates (1131to1135) ofFIG. 11are compared with the certain band ofFIG. 12, and then a candidate most of which is within the certain band1210from among the ground line candidates (1131to1135) is determined as the ground line1310. According to an embodiment, the determining of the ground line1310of the image depends on to what degree each of the plurality of ground line candidates (1131to1135) is within the certain band1210. This determining includes calculating a number of pixels of each of the plurality of ground line candidates (1131to1135) that cross the certain band1210, and determining a ground line that has the greatest number of pixels that lie within the certain band as the ground line1310of the image.