ELECTRONIC DEVICE FOR GENERATING DESCRIPTOR FOR FEATURE POINT, AND OPERATION METHOD THEREOF

The present invention, according to one embodiment, in order to generate a descriptor for a feature point extracted from an input image, may: determine the size of each of a plurality of sub-patches included in a main patch having a preset size on the basis of the feature point in the input image; calculate gradient directions for each pixel constituting a target sub-patch from among the plurality of sub-patches; determine the number of bins for distinguishing the gradient directions; generate, with respect to the target sub-patch, a histogram for a plurality of bins on the basis of the gradient directions of the pixels constituting the target sub-patch; and generate a descriptor for the feature point on the basis of the histogram. Various other embodiments may also be possible.

TECHNICAL FIELD

The following embodiments relate to a method of generating a descriptor of a feature point extracted from an input image, and more particularly, to a descriptor generation method for effective memory management based on a modified scale-invariant feature transform (SIFT) algorithm.

BACKGROUND ART

Various computer vision (CV) technologies for determining matching between images for object detection, tracking, and the like are in development. For example, in the field of CV, technologies such as structure from motion (SfM), visual odometry (VO), and simultaneous localization and mapping (SLAM) may determine image matching based on feature points. They may determine image matching by extracting feature points from input images, generating descriptors representing information about the feature points, and comparing descriptors between multiple images.

In the field of CV, algorithms such as a scale-invariant feature transform (SIFT) algorithm and an oriented FAST (features from accelerated segment test) and rotated BRIEF (binary robust independent elementary features) (ORB) algorithm may be frequently used to extract feature points and generate descriptors. The ORB algorithm may be simpler than the SIFT algorithm because it represents feature points and descriptors only using a difference in brightness values between pixels. However, when an object changes according to various environmental conditions (e.g., lens distortion, angle, lighting, etc.), it may not robustly represent feature points compared to the SIFT algorithm. The SIFT algorithm may configure descriptors more elaborately than the ORB algorithm. However, it may require a great amount of computation or calculation, decreasing the speed, and may use more memory for storing descriptors than the ORB algorithm.

According to the related art, Korean Patent Publication No. 10-1853060 entitled “apparatus and method for determining features invariant under deformation” (applicant: Korea Institute of Science and Technology (KIST)) discloses a method of determining corresponding points that are invariant to image deformation.

DISCLOSURE OF INVENTION

Technical Goals

The computation speed of a scale-invariant feature transform (SIFT) algorithm may be improved by implementing parallel processing using hardware resources. For example, on a field-programmable gate array (FPGA) platform using a system on chip (SoC), the algorithm may extract feature points from images and generate descriptors in real time.

However, in the case of memory, the number of bits of a descriptor to be stored regardless of the platform may be used for determination, and thus, even on the FPGA platform, the SIFT algorithm may still need to use more than four times the memory, compared to an oriented FAST (features from accelerated segment test) and rotated BRIEF (binary robust independent elementary features) (ORB) algorithm.

According to an aspect, there is provided an electronic device and method for reducing memory usage of descriptors in the process of generating descriptors of feature points.

However, the technical aspects are not limited to the preceding aspect(s), and other technical aspects may also be present.

Technical Solutions

According to an embodiment, there is provided a descriptor generation method of generating a descriptor of a feature point extracted from an input image, the descriptor generation method including: determining the size of each of a plurality of sub-patches included in a main patch of a preset size based on the feature point in the input image; calculating a gradient orientation for each of pixels constituting a target sub-patch among the plurality of sub-patches; determining the number of a plurality of bins for dividing the gradient orientation; for the target sub-patch, generating a histogram for the plurality of bins based on the gradient orientation of the pixels constituting the target sub-patch; and generating the descriptor of the feature point based on the histogram.

According to an embodiment, the determining of the size of each of the plurality of sub-patches may include determining the size of each of the plurality of sub-patches based on a resource of a memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the determining the number of the plurality of bins may include determining the number of the plurality of bins based on the resource of the memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the generating of the descriptor of the feature point based on the histogram may include determining the number of bits to be allocated to each of the plurality of bins based on the resource of the memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the feature point may be extracted from the input image based on a scale-invariant feature transform (SIFT) algorithm.

According to an embodiment, the calculating of the gradient orientation may include: performing Gaussian blurring on the main patch using a scale value corresponding to the feature point; and calculating the gradient orientation for each of the pixels included in the target sub-patch.

According to an embodiment, the descriptor generation method may further include, for a representative angle (orientation) calculated in advance for the feature point, subtracting a magnitude of the representative angle from each gradient orientation divided based on the plurality of bins.

According to an embodiment, there is provided an electronic device configured to perform a descriptor generation method of generating a descriptor of a feature point extracted from an input image, the electronic device including: a memory configured to store computer-executable instructions; and a processor configured to execute the instructions by accessing the memory, wherein the instructions cause the processor to: determine the size of each of a plurality of sub-patches included in a main patch of a preset size based on the feature point in the input image; calculate a gradient orientation for each of pixels constituting a target sub-patch among the plurality of sub-patches; determine the number of a plurality of bins for dividing the gradient orientation; for the target sub-patch, generate a histogram for the plurality of bins based on the gradient orientation of the pixels constituting the target sub-patch; and generate the descriptor of the feature point based on the histogram.

According to an embodiment, the instructions cause the processor to determine the size of each of the sub-patches based on a resource of the memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the instructions cause the processor to determine the number of the plurality of bins based on the resource of the memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the instructions cause the processor to determine the number of bits to be allocated to each of the plurality of bins based on the resource of the memory in which the descriptor of the feature point is to be stored.

According to an embodiment, the feature point may be extracted from the input image based on a SIFT algorithm.

According to an embodiment, the instructions cause the processor to: perform Gaussian blurring on the main patch using a scale value corresponding to the feature point; and calculate the gradient orientation for each of the pixels included in the target sub-patch.

According to an embodiment, the instructions cause the processor further to: for a representative angle (orientation) calculated in advance for the feature point, subtract a magnitude of the representative angle from each gradient orientation divided based on the plurality of bins.

According to an embodiment, there is provided an electronic device configured to perform a descriptor generation method of generating a descriptor of a feature point extracted from an input image, the electronic device including: a memory configured to store computer-executable instructions; and a processor configured to execute the instructions by accessing the memory, wherein the instructions cause the processor to: determine the size of each of a plurality of sub-patches included in a main patch of a preset size based on the feature point in the input image, based on a resource of the memory; calculate a gradient orientation for each of pixels constituting a target sub-patch among the plurality of sub-patches; determine the number of a plurality of bins for dividing the gradient orientation, based on the resource of the memory; for the target sub-patch, generate a histogram for the plurality of bins based on the gradient orientation of the pixels constituting the target sub-patch; and generate the descriptor corresponding to the feature point based on the histogram, while determining the number of bits to be allocated to each of the plurality of bins based on the resource of the memory.

According to an embodiment, the instructions cause the processor further to: monitor the resource of the memory in which the descriptor is to be stored.

According to an embodiment, the instructions cause the processor further to: compare a descriptor of at least one feature point of the input image to a descriptor of at least one feature point of another image, and match the input image and the other image; and detect an object based on the matching.

According to an embodiment, the electronic device may be included in a vehicle, wherein the vehicle may be an autonomous vehicle or a vehicle supporting an advanced driver-assistance system (ADAS).

According to an embodiment, the feature point may be extracted from the input image based on a SIFT algorithm.

Effects of Invention

According to various embodiments, there is provided an electronic device and method that may adjust memory usage of descriptors of feature points in various ways.

According to various embodiments, there is provided an electronic device and method that may adjust a method of generating a descriptor of a feature point based on memory resources and may thereby effectively manage the memory resources of a real-time application.

DETAILED DESCRIPTION

Best Mode for Carrying Out Invention

Terms, such as first, second, and the like, are used herein to describe components. These terms are used only to distinguish one component from another component. For example, a first component may be referred to as a second component, or similarly, the second component may also be referred to as the first component.

It should be noted that if it is described that one component is “connected,” “coupled,” or “joined” to another component, a third component may be “connected,” “coupled,” and “joined” between the first and second components, although the first component may be directly connected, coupled, or joined to the second component.

Unless otherwise defined herein, all terms used herein including technical or scientific terms have the same meanings as those generally understood by one of ordinary skill in the art to which this disclosure pertains. Terms, such as those defined in generally used dictionaries, are to be construed to have meanings that are consistent with contextual meanings in the related art and are not to be construed as ideal or excessively formal meanings unless otherwise defined herein.

Hereinafter, example embodiments will be described in detail with reference to the accompanying drawings. When describing the example embodiments with reference to the accompanying drawings, like reference numerals refer to like components and a repeated description related thereto will be omitted.

<Electronic device for generating descriptors of feature points>

FIG.1is a block diagram illustrating an electronic device according to an embodiment.

Referring toFIG.1, an electronic device100configured to generate a descriptor of a feature point extracted from an input image may include a communication unit110, a processor120, and a memory130. The electronic device100may be included in a vehicle that is an autonomous vehicle or a vehicle supporting an advanced driver-assistance system (ADAS).

According to an embodiment, the communication unit110may be connected to the processor120and the memory130to transmit and receive data. The communication unit110may be connected to another external device to receive data, for example, images captured by a camera. The expression transmitting and receiving “A” may be construed herein as transmitting and receiving information or data indicating “A.”

According to an embodiment, the communication unit110may be implemented as circuitry in the electronic device100. For example, the communication unit110may include an internal bus and an external bus. For another example, the communication unit110may be an element that connects the electronic device100and an external device. The communication unit110may be an interface. The communication unit110may receive data from an external device and transmit the data to the processor120and the memory130.

According to an embodiment, the processor120may process the data received by the communication unit110and data stored in the memory130. The “processor” used herein may be a hardware-implemented data processing device having a physically structured circuit to execute desired operations. The desired operations may include, for example, code included in a program or computer-executable instructions. The hardware-implemented data processing device may include, for example, a microprocessor, a central processing unit (CPU), a processor core, a multi-core processor, a multiprocessor, an application-specific integrated circuit (ASIC), and a field-programmable gate array (FPGA).

According to an embodiment, the processor120may execute computer-readable code (e.g., software) stored in a memory (e.g., the memory130) and instructions triggered by the processor120.

According to an embodiment, the memory130may store data received by the communication unit110and data processed by the processor120. For example, the memory130may store a program (or an application or software). The stored program may be a set of syntaxes that are coded to generate a descriptor of a feature point extracted from an input image and executed by the processor120.

According to an embodiment, the memory130may include, for example, at least one volatile memory, non-volatile memory, random-access memory (RAM), flash memory, hard disk drive, and optical disc drive.

According to an embodiment, the memory130may store an instruction set (e.g., software) that operates the electronic device100. The instruction set for operating the electronic device100may be executed by the processor120.

According to an embodiment, the processor120may generate a descriptor of a feature point and store the descriptor in the memory130. The processor120may compare descriptor information about feature points between images and determine whether the images are matched (i.e., image matching).

A process in which the processor120generates a descriptor of a feature point will be described in detail below with reference toFIGS.2A to6.

FIGS.2A and2Bare diagrams illustrating various examples using feature points.

A feature point may be a point that is invariant to the scale (or size), rotation, and brightness of an image, and may be extracted from the same position in the image even if the image rotates or the size or brightness of the image changes. For example, a feature point may be at least one pixel among pixels constituting a background or object in an image.

According to an embodiment, the electronic device100may be provided in an autonomous vehicle or a vehicle supporting an ADAS to receive images around the vehicle using at least one sensor and process the images. For example, the electronic device100may detect an object present around the vehicle or track the detected object in preparation for a potential problem that may occur during driving.

Referring toFIG.2A, when the electronic device100captures consecutive frames210,220, and230, objects215,225, and235that are the same object may be included in the consecutive frames210,220, and230. Tracking an object may require detecting the object included in each frame. The processor120of the electronic device100may detect a feature point in a frame and detect an object based on the detected feature point. According to an embodiment, the processor120of the electronic device100may perform object tracking by detecting the object235in a subsequent frame230corresponding to the object225detected in a current frame220.

FIG.2Bshows an example of detecting the same object by comparing feature points of two images240and250. Referring toFIG.2B, a book in the image250is also included in the image240, and the electronic device100may compare a feature point extracted from the image240and a feature point extracted from the image250to detect the same object. Referring to reference numeral260, the processor120of the electronic device100may compare a descriptor of the feature point extracted from the image240and a descriptor of the feature point extracted from the image250to determine matching between the images240and250. Referring to reference numeral260ofFIG.2B, it may be verified that most feature points, except for some feature points, are properly matched.

A representative example method that may extract a feature point from an image and generate a descriptor may be a scale-invariant feature transform (SIFT) algorithm. A typical descriptor generation process based on the SIFT algorithm will be described in detail below with reference toFIGS.3and4.

FIG.3is a diagram illustrating a typical descriptor generation process based on a SIFT algorithm according to an embodiment.

FIG.4is a diagram illustrating a histogram for a plurality of bins generated based on a gradient orientation according to an embodiment.

According to an embodiment, a descriptor generation method based on the typical SIFT algorithm will be clearly described below with reference toFIGS.3and4.

FIG.3shows a typical process in which a descriptor is generated based on a SIFT algorithm for a feature point extracted from an input image. According to an embodiment, based on the SIFT algorithm, the processor120of the electronic device100may discover a candidate group of feature points, remove unstable feature points during image matching, calculate a representative angle (or orientation) for each feature point, and generate a descriptor of a feature point. The electronic device100may be characterized by a method of generating a descriptor of a feature point, and thus a process of generating a descriptor of a feature point based on the typical SIFT algorithm will be described with reference toFIG.3, and a detailed description of a process of extracting a feature point and calculating a representative angle will be omitted.

According to an embodiment, the processor120may collect images of various scales (or sizes) for an input image based on the SIFT algorithm to generate a scale space, and may perform blurring on the images of the scale space using a Gaussian filter to extract feature points from the images through a difference of Gaussian (DoG) operation. According to an embodiment, the processor120may calculate a representative angle for an extracted feature point based on the SIFT algorithm. According to an embodiment, the processor120may calculate the size and orientation of a gradient for each pixel and determine a representative angle from a histogram generated based on this.

FIG.3shows a typical process of generating a descriptor of a feature point extracted from the SIFT algorithm. According to an embodiment, when using the typical SIFT algorithm, the processor120may determine the size of a sub-patch to be a size of 4×4 pixels in a main patch310that is based on a feature point300. That is, the main patch310based on the feature point300may include 4×4 sub-patches, and each sub-patch (e.g., a target sub-patch330) may include 4×4 pixels320.

According to an embodiment, the processor120may calculate a gradient orientation for each of pixels (e.g., the pixels320) included in a plurality of sub-patches (e.g., the target sub-patch330). For example, the processor120may calculate a gradient orientation for a pixel with coordinates (x, y), based on Equation 1 below.

According to an embodiment, the processor120may calculate gradient orientations for all pixels included in the main patch310and may calculate a gradient orientation for each of the pixels, as shown in the pixels in the main patch310ofFIG.3.

According to an embodiment, the processor120may generate a histogram for a gradient orientation based on each sub-patch (e.g., the target sub-patch330). According to an embodiment, the processor120may generate a histogram based on a gradient orientation (e.g., gradient orientations340calculated from the pixels320) that is calculated for each of the pixels (e.g., the pixels320) included in the target sub-patch330.

According to an embodiment, the processor120may determine the number of a plurality of bins for identifying (or dividing) gradient orientations to generate the histogram, and generate the histogram for the plurality of bins based on the gradient orientation (e.g., the gradient orientations340calculated from the pixels320) calculated for each of the pixels (e.g., the pixels320). For example, in a case in which the number of bins is eight, dividing (or identifying) 360 degrees (°) into eight bins, such as, for example, 0° to 44°, 45° to 89°, . . . , and 315° to 359°, and gradient orientations of pixels included in a sub-patch may be identified (or divided) based on the plurality of bins.

For example,FIG.4shows a histogram generated in a case in which the number of bins is 36 according to an embodiment. According to an embodiment, when determining the number of bins as 36, the processor120may generate a histogram in which 360° is divided into 36 bins and gradient orientations of pixels are included in corresponding bins. For example, when a gradient orientation of a pixel is 25°, it may correspond to bin410of the histogram shown inFIG.4. According to an embodiment, a distribution of gradient orientations (e.g.,370ofFIG.3) may be expressed based on a histogram, and a larger number of bins (e.g., bins410and450ofFIG.4) may be expressed as longer arrows.

According to an embodiment, a distribution of gradient orientations may be expressed for each sub-patch based on a histogram. For example, in the main patch310, a histogram may be generated for each sub-patch (e.g., a target sub-patch360), as shown in a main patch350, and a distribution of gradient orientations (e.g.,370ofFIG.3) may be expressed based on the histogram for each sub-patch. For example, reference numeral370ofFIG.3shows a division of gradient orientations of pixels in the sub-patch360based on eight bins. The number of pixels included in the eight bins, for example, 0° to 44°, 45° to 89°, . . . , and 315° to 359°, may be expressed as arrows in orientations of 0°, 45°, . . . , and 315°, respectively.

According to an embodiment, the processor120may generate a descriptor of the feature point300based on the histogram. According to an embodiment, the processor120may generate the descriptor of the feature point300based on the distribution of gradient orientations of pixels. For example, referring toFIG.3, there may be the number of histograms (or the distribution370of gradient orientations expressed based on the histogram) corresponding to the number of sub-patches (e.g., the target sub-patch360) for the feature point300, and the processor120may generate the descriptor based on the eight bins for each of 4×4 sub-patches according to the typical SIFT algorithm. The processor120may generate the descriptor of a size (128 byte=the number of sub-patches (4×4)×the number of bins (8)×the number of bits allocated to one bin (8)).

In the case of a real-time application to which image matching is applied in real time, the memory capacity required to store descriptors may become excessively large as images are accumulated. According to an embodiment, the processor120of the electronic device100may generate a descriptor of a smaller size than in the typical SIFT algorithm, based on a modified SIFT algorithm. For example, the processor120may determine the size of a sub-patch, determine the number of bins, and determine the number of bits to be allocated to a bin, thereby adaptively adjusting the size of the descriptor. According to various embodiments, a method by which the processor120generates a descriptor based on the modified SIFT algorithm will be described in detail below with reference toFIGS.5and6.

FIG.5is a diagram illustrating an operation of generating a descriptor by changing the size of a sub-patch according to an embodiment.

FIG.5shows a main patch510of a feature point500to which a typical SIFT algorithm is applied and a main patch550of the feature point500to which a modified SIFT algorithm is applied. The respective sizes of the main patches510and550may be the same as a preset size. According to an embodiment, the processor120may change the size of a sub-patch for the main patch550to be different from that of the main patch510.

For example, in the case of a descriptor generation method based on the typical SIFT algorithm, 4×4 sub-patches (e.g., sub-patches520) may be determined for the main patch510of the preset size, but the processor120may determine 2×2 sub-patches (e.g., sub-patches560) for the main patch550based on the modified SIFT algorithm. That is, the processor120may determine the size of a sub-patch to be 8×8 pixels, rather than 4×4 pixels. According to an embodiment, the processor120may determine the size of a sub-patch based on a resource of the memory130. According to another embodiment, the processor120may monitor the resource of the memory130and adjust the size of a sub-patch based on the resource of the memory130in real time.

According to an embodiment, in a case of dividing the main patch510into the 4×4 sub-patches520according to the typical SIFT algorithm, a processor may generate a descriptor of a size (128 byte=the number of sub-patches (4×4)×the number of bins (8)×the number of bits allocated to one bin (8)).

According to an embodiment, based on the modified SIFT algorithm, the processor120may divide the main patch550into the 2×2 sub patches560, and generate a descriptor of a size (32 byte=the number of sub-patches (2×2)×the number of bins (8)×the number of bits allocated to one bin (8)).

According to an embodiment, in a case of changing the size of a sub-patch as shown in reference numeral550ofFIG.5, a capability to express in detail a descriptor may decrease, but the descriptor may be more robust against sensor noise or pixel deterioration. According to an embodiment, when generating a descriptor based on the modified algorithm, the processor120may use a smaller memory capacity to store the descriptor.

FIG.6is a diagram illustrating an operation of generating a descriptor by changing the number of bins for identifying (or dividing) a gradient orientation according to an embodiment.

FIG.6shows a main patch610for a feature point600to which a typical SIFT algorithm is applied and main patches640and670for the feature point600to which a modified SIFT algorithm is applied. According to an embodiment, the processor120may change the number of bins for the main patches640and670to be different from that for the main patch610.

For example, in the case of a descriptor generation method based on the typical SIFT algorithm, a gradient orientation may be divided into eight bins for each sub-patch (e.g., sub-patches615) of the main patch610, but the processor120based on the modified SIFT algorithm may divide a gradient orientation into four bins for each sub-patch (e.g., sub-patches645) of the main patch640. According to another embodiment, the processor120based on the modified SIFT algorithm may divide a gradient orientation into two bins for each sub-patch (e.g., sub-patches675) of the main patch670.

According to an embodiment, the processor120may determine the number of bins based on a resource of the memory130. According to another embodiment, the processor120may monitor the resource of the memory130to adjust the number of bins for identifying (or dividing) a gradient orientation according to the memory resource in real time.

According to an embodiment, as described above with reference toFIGS.3and4, a processor based on the typical SIFT algorithm may generate a descriptor of a size (128 byte=the number of sub-patches (4×4)×the number of bins (8)×the number of bits allocated to one bin (8)).

According to an embodiment, the processor120based on the modified SIFT algorithm may divide a gradient orientation into four bins in each sub-patch (e.g., the sub-patches645) of the main patch640, and generate a descriptor of a size (64 byte=the number of sub-patches (4×4)×the number of bins (4)×the number of bits allocated to one bin (8)).

According to an embodiment, the processor120based on the modified SIFT algorithm may divide a gradient orientation into two bins in each sub-patch (e.g., the sub-patches675) of the main patch670, and generate a descriptor of a size (32 byte=the number of sub-patches (4×4)×the number of bins (2)×the number of bits allocated to one bin (8)).

According to an embodiment, in the case of changing the number of bins as shown in reference numeral645or675ofFIG.6, a capability of a descriptor to express a gradient orientation may be reduced, but the size of the sub-patches645and675may be maintained, and thus a capability to identify (or divide) the main patches640and670may be maintained. According to examination, using four bins in simultaneous localization and mapping (SLAM) may not degrade matching performance, compared to using eight bins, and there may only be an insignificant degradation in matching performance even using two bins. According to an embodiment, when the processor120generates a descriptor based on the modified algorithm, it may use only a smaller memory capacity to store the descriptor.

According to an embodiment, the processor120based on the modified SIFT algorithm may reduce memory usage by determining the number of bits allocated to one bin, in addition to the embodiments described above with reference toFIGS.5and6. For example, in the case of the typical SIFT algorithm, 8 bits (=1 byte) may be allocated to one bin, but in the case of the modified SIFT algorithm, the processor120may allocate 2 or 4 bits to one bin.

According to an embodiment, when changing only the number of bits allocated to a bin to 2 or 4 bits while maintaining the size of a sub-patch at 4×4 pixels, the processor120may generate a descriptor of a size (32 byte=the number of sub-patches (4×4)×the number of bins (8)×the number of bits allocated to one bin (2)) or of a size (64 byte=the number of sub-patches (4×4)×the number of bins (8)×the number of bits allocated to one bin (4)), rather than a descriptor of a previous size (128 byte).

According to an embodiment, when the processor120changes the number of bits allocated to each bin based on the modified algorithm, positional and directional identifying capabilities may be maintained, and matching performance may thus be maintained. According to an embodiment, when based on the modified algorithm, the processor120may use a smaller memory capacity to store a descriptor. According to an embodiment, the processor120may adaptively adjust memory usage when storing a descriptor.

According to an embodiment, the processor120may generate a descriptor using various combinations of the preceding methods—the method of determining the size of a sub-patch, the method of determining the number of bins, and the method of determining the number of bits allocated to a bin, according to a memory resource. For example, the processor120may determine the size of a sub-patch to be 8×8 pixels to form a main patch of a preset size with 2×2 sub-patches, determine the number of bins to be four, and determine the number of bits to be allocated to each bin to be 4 bits, thereby generating a descriptor of a size (8 byte=the number of sub-patches (2×2)×the number of bins (4)×the number of bits allocated to one bin (4)).

<Method of Generating Descriptors of Feature Points>

FIG.7is a flowchart illustrating a descriptor generation method of an electronic device according to an embodiment.

Operations710to750described below may be performed by the processor120of the electronic device100described above with reference toFIG.1, and the related description provided above with reference toFIGS.1to6will not be repeated for conciseness.

According to an embodiment, in operation710, the processor120may determine the size of each of a plurality of sub-patches included in a main patch of a preset size based on a feature point in an input image.

According to an embodiment, as described above with reference toFIG.5, the processor120may determine the size of a sub-patch for a main patch of an input preset size, thereby reducing the capacity to generate a descriptor of a feature point.

According to an embodiment, in operation720, the processor120may calculate a gradient orientation for each of pixels constituting a target sub-patch among the plurality of sub-patches. According to an embodiment, as described above with reference to the main patch310ofFIG.3, the processor120may calculate a gradient orientation for each of pixels included in sub-patches constituting a main patch.

According to an embodiment, in operation730, the processor120may determine the number of a plurality of bins for identifying (or dividing) the gradient orientation. As described above with reference toFIG.6, the processor120may determine the number of bins to be eight, two, or four.

According to an embodiment, in operation740, the processor120may generate a histogram for the plurality of bins based on the gradient orientation of the pixels constituting the target sub-patch. According to an embodiment, as described above with reference toFIG.4, the processor120may identify (or divide) 0° to 359° into a plurality of bins and allocate gradient orientations of the pixels of the target sub-patch to the bins.

According to an embodiment, in operation750, the processor120may generate a descriptor of a feature point based on the histogram. According to an embodiment, as described above with reference toFIGS.3and4, the processor120may generate the descriptor of the feature point and determine the capacity of the descriptor generated for the feature point. According to an embodiment, in operation750, the processor120may determine the number of bits to be allocated to each bin. According to an embodiment, as described above with reference toFIGS.5and6, the processor120may generate the descriptor based on the size of sub-patches for the main patch of the preset size, the number of bins, and the number of bits allocated to each bin, and calculate the capacity. According to an embodiment, the processor120may generate the descriptor and store the generated descriptor in the memory130.

FIG.8is a flowchart illustrating a descriptor generation method based on a memory resource according to an embodiment.

Operations810to850described below may be performed by the processor120of the electronic device100described above with reference toFIG.1, and the related description provided above with reference toFIGS.1to7will not be repeated for conciseness.

According to an embodiment, operations810to850described below may correspond to operations (e.g., operations710to750ofFIG.7) described above with reference toFIG.7, and the repeated description thereof will be omitted.

According to an embodiment, in operation810, the processor120may determine the size of each of a plurality of sub-patches included in a main patch of a preset size based on a feature point in an input image, based on a resource of the memory130. For example, when the resource of the memory130is less than a threshold value, the processor120may determine the size of each sub-patch to be greater (e.g., 8×8 pixels) than a reference size (e.g., 4×4 pixels) for the main patch of the preset size. As described above with reference toFIG.5, the processor120may determine the size of each sub-patch to be larger, thereby reducing the capacity of a descriptor generated for the feature point.

According to an embodiment, in operation820, the processor120may calculate a gradient orientation for each of pixels constituting a target sub-patch among the plurality of sub-patches. Operation820may be the same as operation720, and thus a more detailed description thereof will be omitted.

According to an embodiment, in operation830, the processor120may determine the number of a plurality of bins for identifying (or dividing) the gradient orientation based on the resource of the memory130. For example, when the resource of the memory130is less than the threshold value, the processor120may determine the number (e.g., four based on 90° or two based on 180°) of bins to less than a reference number (e.g., eight based on 45°). As described above with reference toFIG.6, the processor120may determine the number of bins to be less than the reference number, thereby reducing the capacity of the descriptor generated for the feature point.

According to an embodiment, in operation840, the processor120may generate a histogram for the plurality of bins based on the gradient orientation of each of the pixels constituting the target sub-patch, for the target sub-patch. Operation840may be the same as operation740, and thus a more detailed description thereof will be omitted.

According to an embodiment, in operation850, when generating the descriptor of the feature point based on the histogram, the processor120may determine the number of bits to be allocated to each of the plurality of bins based on the resource of the memory130. For example, when the resource of the memory130is less than the threshold value, the processor120may determine the number of bits (e.g., 4 bits or 2 bits) allocated to each bin to be less than a reference number of bits (e.g., 8 bits). As described above with reference toFIG.6, the processor120may determine the number of bits allocated to each of the plurality of bins to be less than the reference number of bits, thereby reducing the capacity of the descriptor generated for the feature point.

According to an embodiment, the processor120may monitor the resource of the memory130in real time and may adaptively adjust the size of each of the plurality of sub-patches, the number of the plurality of bins, and the number of bits allocated to each of the plurality of bins, based on a result of the monitoring.

FIG.9is a flowchart illustrating an operation of calculating a gradient orientation by an electronic device according to an embodiment.

Operations910and920described below may be performed by the processor120of the electronic device100described above with reference toFIG.1, and the related description provided above with reference toFIGS.1to8will not be repeated for conciseness.

According to an embodiment, operations910and920may correspond to an operation (e.g., operation720ofFIG.7) of calculating a gradient orientation for each of pixels constituting a target sub-patch among a plurality of sub-patches, which is described above with reference toFIG.7. According to an embodiment, operations910and920may correspond to an operation (e.g., operation820ofFIG.8) of calculating a gradient orientation for each of pixels constituting a target sub-patch among a plurality of sub-patches, which is described above with reference toFIG.8.

According to an embodiment, in operation910, the processor120may perform Gaussian blurring on a main patch of a preset size based on a feature point, using a scale value corresponding to the feature point. According to an embodiment, a scale value (or a scale parameter) corresponding to a feature point may be determined in advance based on a SIFT algorithm. According to an embodiment, the greater the scale value, the greater the level of blurring.

According to an embodiment, in operation920, the processor120may calculate a gradient orientation for each of pixels included in a target sub-patch. According to an embodiment, in operation920, the processor120may also calculate a gradient size for each of the pixels according to the SIFT algorithm and weight the gradient size based on a Gaussian filter. Using the Gaussian filter, the gradient size of pixels close to the feature point may increase, and the gradient size of pixels far from the feature point may decrease.

FIG.10is a flowchart illustrating a post-processing operation after descriptor generation by an electronic device according to an embodiment.

Operation1010described below may be performed by the processor120of the electronic device100described above with reference toFIG.1, and the related description provided above with reference toFIGS.1to9will not be repeated for conciseness.

According to an embodiment, in operation1010, the processor120may perform post-processing on a generated descriptor. For example, the processor120may subtract a magnitude of a representative angle calculated in advance for a feature point, from each gradient orientation divided based on a plurality of bins. The processor120may perform operation1010such that pixels around the feature point include only direction information relative to the feature point and the feature point becomes invariant to rotation (i.e., rotation invariance).

According to an embodiment, the processor120may perform normalization as the post-processing on the descriptor. The normalization may maintain relative brightness and allow the feature point to be invariant to brightness (i.e., brightness invariance).

According to an embodiment, after the post-processing in operation1010, the processor120may compare descriptors of feature points of a plurality of input images and determine whether the images are matched. According to an embodiment, the electronic device100may be included in a vehicle that is an autonomous vehicle or a vehicle supporting an ADAS, and the processor120may determine image matching in real time for images around the vehicle using a modified SIFT algorithm described above with reference toFIGS.1to9. The processor120may generate descriptors based on the modified SIFT algorithm, thereby adaptively controlling memory usage and efficiently managing memory resources.

The above-described hardware devices may be configured to act as one or more software modules in order to perform the operations of the above-described examples, or vice versa.