KR20130142191A - Robust feature matching for visual search - Google Patents
Robust feature matching for visual search Download PDFInfo
- Publication number
- KR20130142191A KR20130142191A KR1020137030249A KR20137030249A KR20130142191A KR 20130142191 A KR20130142191 A KR 20130142191A KR 1020137030249 A KR1020137030249 A KR 1020137030249A KR 20137030249 A KR20137030249 A KR 20137030249A KR 20130142191 A KR20130142191 A KR 20130142191A
- Authority
- KR
- South Korea
- Prior art keywords
- computed
- group
- distances
- query
- feature
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Abandoned
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/50—Information retrieval; Database structures therefor; File system structures therefor of still image data
- G06F16/58—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F16/583—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F18/00—Pattern recognition
- G06F18/20—Analysing
- G06F18/24—Classification techniques
- G06F18/241—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches
- G06F18/2413—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches based on distances to training or reference patterns
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- Library & Information Science (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Evolutionary Computation (AREA)
- Evolutionary Biology (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Bioinformatics & Computational Biology (AREA)
- Artificial Intelligence (AREA)
- Life Sciences & Earth Sciences (AREA)
- Databases & Information Systems (AREA)
- Image Analysis (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
비주얼 탐색을 위한 강건한 특징 매칭을 수행하기 위한 기법들이 기재된다. 인터페이스 및 특징 매칭 유닛을 포함하는 장치가 이들 기법들을 구현한다. 인터페이스는 질의 특징 기술자를 수신한다. 특징 매칭 유닛은 이어서 질의 특징 기술자와 기준 특징 기술자들 간의 거리를 컴퓨팅하고 클러스터링 알고리즘에 따라 컴퓨팅된 거리들의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정한다. 특징 매칭 유닛은 이어서 컴퓨팅된 거리들의 결정된 제 1 그룹 및 제 2 그룹에 기초하여 질의 특징 기술자가 컴퓨팅된 거리들 중 최소의 것에 연관되는 기준 특징 기술자들 중 하나에 매칭하는지를 결정한다. Techniques for performing robust feature matching for visual search are described. An apparatus including an interface and feature matching unit implements these techniques. The interface receives a query feature descriptor. The feature matching unit then computes the distance between the query feature descriptor and the reference feature descriptors and determines a first group of computed distances and a second group of computed distances according to a clustering algorithm. The feature matching unit then determines whether the query feature descriptor matches one of the reference feature descriptors associated with the least of the computed distances based on the determined first and second groups of computed distances.
Description
[0001] 본 개시는 영상 프로세싱 시스템들에 관한 것으로서, 보다 구체적으로는, 영상 프로세싱 시스템들을 통해 비주얼 탐색들을 수행하는 것에 관한 것이다. TECHNICAL FIELD The present disclosure relates to image processing systems, and more particularly, to performing visual searches through image processing systems.
[0002] 컴퓨팅 디바이스들 또는 컴퓨터들의 맥락에서 비주얼 탐색(visual search)은 컴퓨터 또는 다른 디바이스가 하나 이상의 영상들 내의 다른 객체들 및/또는 특징들 사이에서 객체들 및/또는 특징들에 대한 탐색을 수행하는 것을 가능하게 하는 기법들을 지칭한다. 비주얼 탐색에 있어서의 최근의 관심은 영상 스케일의 변경들, 노이즈, 조명 및 로컬 지오메트리 왜곡을 포함하는 매우 다양한 변하는 영상 조건들에서 부분적으로 차폐된 객체들 및/도는 특징들을 컴퓨터가 식별하는 것을 가능하게 하는 알고리즘들을 발생시켰다. 이 동일한 시간 동안, 텍스트를 입력하거나 모바일 디바이스들과 다른 방식으로 인터페이싱하기 위한 제한된 사용자 인터페이스들을 가질 수 있지만 카메라들을 피처링(feature)하는 모바일 디바이스들이 출현하였다. 모바일 디바이스들 및 모바일 디바이스 애플리케이션들의 개발자들은 모바일 디바이스와의 사용자 상호작용을 강화하기 위해 모바일 디바이스의 카메라를 활용하고자 하였다. Visual search in the context of computing devices or computers allows a computer or other device to search for objects and / or features among other objects and / or features in one or more images. Refers to techniques that make it possible to do so. Recent interest in visual search has enabled the computer to identify partially shielded objects and / or features in a wide variety of changing imaging conditions, including changes in image scale, noise, lighting and local geometry distortion. Generated algorithms. During this same time, mobile devices have emerged that feature limited camera interfaces for entering text or otherwise interfacing with mobile devices. Developers of mobile devices and mobile device applications have sought to leverage the camera of a mobile device to enhance user interaction with the mobile device.
[0003] 일 강화를 예시하기 위해, 모바일 디바이스의 사용자는 상점에서 쇼핑하는 동안 임의의 정해진 물건의 영상을 캡처하도록 모바일 디바이스의 카메라를 활용할 수 있다. 모바일 디바이스는 이어서 매칭하는 기준 영상에 기초하여 영상("탐색 영상"으로서 지칭될 수 있음)에서 도시되는 물건을 식별하도록 다양한 기준 영상들에 대한 아카이빙된 특징 기술자들(archived feature descriptors)의 세트 내에서 비주얼 탐색 알고리즘을 시작할 수 있다. 물건을 식별한 이후, 모바일 디바이스는 이어서 인터넷의 탐색을 시작하고 물건이 근처의 상인들 및/또는 온라인 상인들로부터 이용 가능한 최저 가격을 포함해서 식별된 물건에 관한 정보를 포함하는 웹페이지를 제시할 수 있다. 이러한 방식으로, 사용자는 키보드(사용자가 인터페이스하는 영상으로서 터치 스크린 상에 그것이 제시된다는 점에서 종종 "가상" 키보드임) 또는 다른 입력 매커니즘을 통해 모바일 디바이스와 인터페이스해야만 할 필요성을 방지할 수 있지만, 비주얼 탐색 및 후속 웹페이지 탐색들을 개시하기 위해 탐색 영상을 단지 캡처할 수 있다. To illustrate one enhancement, a user of a mobile device may utilize the camera of the mobile device to capture an image of any given item while shopping in a store. The mobile device is then within a set of archived feature descriptors for the various reference images to identify the object shown in the image (which may be referred to as a "navigation image") based on the matching reference image. You can start the visual search algorithm. After identifying the object, the mobile device may then begin searching the Internet and present a webpage that contains information about the identified object, including the lowest price available from nearby merchants and / or online merchants. Can be. In this way, the user can avoid the need to interface with the mobile device through a keyboard (which is often a "virtual" keyboard in that it is presented on a touch screen as the image the user interfaces) or other input mechanism, but visual The search image may only be captured to initiate the search and subsequent webpage searches.
[0004] 비주얼 탐색에 대한 액세스 및 카메라가 장착된 모바일 디바이스가 이용할 수 있는 다수의 애플리케이션들이 있지만, SIFT(scale invariant feature transform) 알고리즘과 같은 비주얼 탐색을 구현하기 위한 비주얼 탐색 알고리즘들은 특징 매칭을 수행하는 견지에서 부족할 수 있다. 특징 매칭은 탐색 영상으로부터 추출된 탐색 특징 기술자들이 기준 영상들로부터 추출된 기준 특징 기술자들에 대해 매칭되는 비주얼 탐색 알고리즘의 양상을 지칭한다. Although there are many applications that can be used by mobile devices equipped with cameras and access to visual navigation, visual search algorithms for implementing visual search, such as a scale invariant feature transform (SIFT) algorithm, perform feature matching. May be lacking in terms of Feature matching refers to an aspect of a visual search algorithm in which search feature descriptors extracted from a search image are matched against reference feature descriptors extracted from reference images.
[0005] 이러한 부족들을 예시하기 위해, 탐색 특징 기술자 및 기준 특징 기술자들이 각각 빌딩을 가로질러 반복하는 특유의 아치들 또는 창문들과 같이 탐색 및 기준 영상들의 반복하는 특징으로부터 추출될 때의 인스턴스들에서, 그렇지 않았다면 탐색 특징 기술자에 매칭했었을 기준 특징 기술자를 폐기할 수 있는 SIFT 알고리즘을 고려한다. 또한, SIFT 알고리즘은 공통적으로 임의의 정해진 비주얼 탐색에 응답하여 단일의 영상만을 리턴하며, 여기서 이러한 리턴된 영상은 SIFT 알고리즘에 의해 알고리즘적으로 "최상의 매칭"인 것으로 결정된다. 그러나 사용자들은 단일의 SIFT 최상의 매칭 결과가 사용자의 기대에 매칭하지 않을 수 있기 때문에 사용자를 좌절시킬 수 있는 SIFT 알고리즘과 동일한 방식으로 "최상의 매칭"를 무엇이 구성하는지를 결정할 수 없을 수 있다. To illustrate these deficiencies, in the instances when the search feature descriptor and the reference feature descriptors are extracted from the repeating feature of the search and reference images, such as the distinct arches or windows that repeat across the building, respectively. Consider an SIFT algorithm that can discard reference feature descriptors that would otherwise have matched the search feature descriptors. In addition, the SIFT algorithm commonly returns only a single image in response to any given visual search, where this returned image is determined to be "best match" algorithmically by the SIFT algorithm. However, users may not be able to determine what constitutes "best match" in the same way as a SIFT algorithm that can be frustrating because a single SIFT best match result may not match the user's expectations.
[0006] 일반적으로, 본 개시는 비주얼 탐색을 수행할 때 특징 매칭을 용이하게 하는 기법들을 기술한다. 이 기법들은 탐색 결과들의 랭크된 리스트들을 제공할 수 있는 특징 매칭 알고리즘을 제공함으로써 특징 매칭을 개선할 수 있다. 기법들은 반복 특징들을 수용하는 특징 매칭 알고리즘을 제공함으로써 강건성을 개선할 수 있다. 현재 탐색 특징 기술자와 매칭하는 2개 이상의 기준 특징들이 서로 근접하게 위치될 때 기준 특징 기술자들을 거절하기 보단 오히려, 예를 들어, SIFT 알고리즘에 의해 제공되는 바와 같이(2개 이상의 매칭 기준 특징 기술자들이 너무 가까운 경우, 이들 매칭 기준 특징 기술자들은 고유할 가능성이 적고 이에 따라 탐색 영상의 분류를 용이하게 할 가능성이 적다는 전제 하에서), 기법들은 특징 매칭을 수행할 때 고유성을 보다 적절히 결정하기 위해 클러스터링 알고리즘들을 활용할 수 있다. 또한, 기법들은 종래의 비주얼 탐색 알고리즘들에서 공통적인 바와 같이 단일의 기준 영상을 단순히 리턴하기 보단 오히려 매칭 기준 영상들의 랭크된 리스트의 생성 및 리턴을 용이하게 할 수 있다. 매칭 기준 영상들의 랭크된 리스트는 최상의 매칭을 구성하는 것의 알고리즘 결정을 수용하도록 강제되기 보단 오히려, "최상의 매칭"으로서 사용자가 고려하는 것을 선택하는 기뢰를 사용자에게 제공할 수 있다. In general, the present disclosure describes techniques for facilitating feature matching when performing a visual search. These techniques can improve feature matching by providing a feature matching algorithm that can provide ranked lists of search results. The techniques can improve robustness by providing a feature matching algorithm that accommodates iterative features. Rather than rejecting the reference feature descriptors when two or more reference features matching the current search feature descriptor are located in close proximity to each other, for example, as provided by the SIFT algorithm (two or more matching reference feature descriptors are too large). In the near term, under the premise that these matching criteria feature descriptors are less likely to be unique, and thus less likely to facilitate classification of search images), the techniques employ clustering algorithms to more appropriately determine uniqueness when performing feature matching. It can be utilized. In addition, the techniques may facilitate generation and return of a ranked list of matching reference images rather than simply returning a single reference image as is common in conventional visual search algorithms. Rather than being forced to accept an algorithmic decision of what constitutes the best match, the ranked list of matching reference images may provide the user with a mine to choose what the user considers as “best match”.
[0007] 일 예에서, 비주얼 탐색 디바이스를 통해 비주얼 탐색을 수행하기 위한 방법으로서, 이 방법은 상기 비주얼 탐색 디바이스를 통해, 비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하는 단계를 포함하고, 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시한다. 이 방법은 또한 상기 비주얼 탐색 디바이스를 통해, 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하는 단계를 포함하고 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함한다. 이 방법은 추가로 상기 비주얼 탐색 디바이스를 통해, 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계를 포함한다. In one example, a method for performing a visual search via a visual search device, the method comprising, via the visual search device, a query feature descriptor provided by a visual search query and a plurality of reference features. Computing a distance between each of the descriptors, wherein the visual search query initiates the visual search. The method also includes determining, via the visual navigation device, one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm. The group includes those of computed distances indicating that the associated of the plurality of reference feature descriptors is near to the query feature descriptor relative to those of the computed distances determined to be within the second group of computed distances. The second group of distances includes those of computed distances indicating that the associated of the plurality of reference feature descriptors is away from the query feature descriptor relative to those of the computed distances determined to be within the first group of computed distances. . The method further includes, via the visual navigation device, a plurality of query feature descriptors associated with the least of the computed distances based on the determined first group of computed distances and the second group of computed distances. And determining whether to match one of the reference feature descriptors of.
[0008] 다른 예로서, 비주얼 탐색을 수행하기 위한 장치는 비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하기 위한 수단을 포함하며, 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시한다. 이 장치는 또한 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하기 위한 수단을 포함하고 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함한다. 이 장치는 추가로 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계를 포함한다. As another example, an apparatus for performing a visual search includes means for computing a distance between each of a plurality of reference feature descriptors and a query feature descriptor provided by a visual search query, wherein the visual The search query initiates the visual search. The apparatus also includes means for determining one or more first groups of computed distances and a second group of computed distances in accordance with a clustering algorithm wherein the first group of computed distances is determined by the plurality of criteria. The second group of computed distances includes those of computed distances indicating that an association of feature descriptors is near to the query feature descriptor relative to those of the computed distances determined to be within the second group of computed distances. The associated of the plurality of reference feature descriptors includes those of computed distances indicating that the query feature descriptor is away from those of the computed distances determined to be within the first group of computed distances. The apparatus further includes one of a plurality of reference feature descriptors in which the query feature descriptor is associated with the least of the computed distances based on the determined first group of computed distances and the second group of computed distances. Determining whether to match.
[0009] 다른 예에서, 비주얼 탐색을 수행하기 위한 장치는 질의 특징 기술자를 수신하는 인터페이스, 및 특징 매칭 유닛을 포함하고, 상기 특징 매칭 유닛은 비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하도록 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ; 및 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하도록; 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하도록 구성된다. In another example, an apparatus for performing a visual search includes an interface to receive a query feature descriptor, and a feature matching unit, wherein the feature matching unit is a query feature descriptor provided by a visual search query. And compute a distance between each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search; And determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm; The first group of computed distances is computed to indicate that an associated of the plurality of reference feature descriptors is near to the query feature descriptor as compared to those of the computed distances determined to be within the second group of computed distances. A second group of computed distances, including those of distances, indicating that an associated of the plurality of reference feature descriptors is away from the query feature descriptor relative to those of the computed distances determined to be within the first group of computed distances. Includes those of computed distances; And based on the determined first group of computed distances and the second group of computed distances, determine whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the least of the computed distances. It is configured to.
[0010] 다른 예에서, 컴퓨터-판독 가능한 매체는 명령을 포함하고, 상기 명령은 실행될 때, 하나 이상의 프로세서들로 하여금, 비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하게 하고 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ; 및 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하게 하고 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하게 한다. In another example, a computer-readable medium includes instructions that, when executed, cause the one or more processors to execute a query feature descriptor and a plurality of reference features provided by a visual search query. Compute a distance between each of the descriptors, wherein the visual search query initiates the visual search; And determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is associated with the plurality of reference feature descriptors. And those of computed distances indicating that the query feature descriptor is near relative to those of the computed distances determined to be within the second group of computed distances, wherein the second group of computed distances is the plurality of reference feature descriptors. Includes those of computed distances indicating that the association of the distance from the query feature descriptor is relative to those of the computed distances determined to be within the first group of computed distances; And based on the determined first group of computed distances and the second group of computed distances, determine whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the least of the computed distances. Let's do it.
[0011] 다른 예로서, 시스템은 비주얼 탐색을 개시하기 위한 탐색 질의에 의해 질의 특징 기술자를 전송하는 클라이언트 디바이스, 복수의 기준 질의 기술자를 저장하는 데 및 비주얼 탐색을 수행하는 비주얼 탐색 서버 디바이스를 포함한다. 비주얼 탐색 서버는 탐색 질의에 의해 질의 특징 기술자를 수신하는 인터페이스 및 특징 매칭 유닛을 포함하고, 상기 특징 매칭 유닛은 질의 특징 기술자와 상기 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하고; 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하고 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 인터페이스를 포함한다. As another example, a system includes a client device that sends a query feature descriptor by a search query to initiate a visual search, a plurality of reference query descriptors, and a visual search server device that performs the visual search. . The visual search server includes an interface and a feature matching unit to receive a query feature descriptor by a search query, the feature matching unit computing a distance between a query feature descriptor and each of the plurality of reference feature descriptors; Determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is associated with the plurality of reference feature descriptors. Including those of computed distances indicating that the query feature descriptor is near relative to those of the computed distances determined to be within a second group of distances, and wherein the second group of computed distances are associated with the plurality of reference feature descriptors. Includes those of computed distances indicating that the one is farther from the query feature descriptor compared to those of the computed distances determined to be within the first group of computed distances; And based on the determined first group of computed distances and the second group of computed distances, determine whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the least of the computed distances. Contains the interface to
[0012] 하나 이상의 예들의 상세들은 아래의 첨부 도면 및 설명에서 기술된다. 다른 특징들, 목적들 및 이점들은 설명 및 도면 및 청구범위로부터 자명하게 될 것이다.
Details of one or more examples are set forth in the accompanying drawings and the description below. Other features, objects, and advantages will be apparent from the description and drawings, and from the claims.
도 1은 본 개시에서 기술되는 강건한 특징 기술자 매칭 기법들을 구현하는 영상 프로세싱 시스템을 예시하는 블록도.
도 2는 도 1의 특징 매칭 유닛을 보다 상세히 예시하는 블록도.
도 3a 및 도 3b는 본 개시에서 기술되는 특징 매칭 기법들을 구현하는데 있어 비주얼 탐색 서버의 예시적인 동작을 예시하는 흐름도.
도 4는 키포인트 추출을 수행하는데 이용하기 위한 DoG(difference of Gaussian) 피라미드를 특징 추출 유닛이 결정하는 프로세스를 예시하는 다이어그램.
도 5는 DoG(difference of Gaussian) 피라미드를 결정한 이후 키포인트의 검출을 예시하는 다이어그램.
도 6은 특징 추출 유닛이 그라디언트 분포 및 방위 히스토그램을 결정하는 프로세스를 예시하는 다이어그램.
도 7은 특징 추출 유닛이 그라디언트 분포 및 방위 히스토그램을 결정하는 프로세스를 예시하는 다이어그램.1 is a block diagram illustrating an image processing system implementing the robust feature descriptor matching techniques described in this disclosure.
2 is a block diagram illustrating the feature matching unit of FIG. 1 in more detail.
3A and 3B are flow diagrams illustrating exemplary operation of a visual search server in implementing the feature matching techniques described in this disclosure.
4 is a diagram illustrating a process by which a feature extraction unit determines a difference of Gaussian (DoG) pyramid for use in performing keypoint extraction.
5 is a diagram illustrating detection of a keypoint after determining a difference of Gaussian (DoG) pyramid.
6 is a diagram illustrating a process by which a feature extraction unit determines a gradient distribution and an orientation histogram.
7 is a diagram illustrating a process by which a feature extraction unit determines a gradient distribution and an orientation histogram.
[0020] 도 1은 본 개시에서 기술되는 강건한 특징 매칭 기법들을 구현하는 영상 프로세싱 시스템(10)을 예시하는 블록도이다. 도 1의 예에서, 영상 프로세싱 시스템(10)은 클라이언트 디바이스(12), 비주얼 탐색 서버(14) 및 네트워크(16)를 포함한다. 클라이언트 디바이스(12)는 이 예에서, 랩톱, 이른바 넷북, 개인 휴대 정보 단말(PDA), 셀룰러 또는 모바일 전화 또는 핸드셋(이른바 "스마트폰들"로 불림), GPS(global positioning system) 디바이스, 디지털 카메라, 디지털 미디어 재생기, 게임 디바이스, 또는 비주얼 탐색 서버(14)와 통신할 수 있는 임의의 다른 모바일 디바이스와 같은 모바일 디바이스를 이 예에서 표현한다. 본 개시에서 비주얼 탐색 서버(14)에 대해 기술되지만, 본 개시에서 기술되는 기법들은 비주얼 탐색 서버들로 제한되어선 안 된다. 대신, 기법들은 로컬 특징-기반 비주얼 탐색 알고리즘들의 특징 매칭 양상들을 구현할 수 있는 임의의 디바이스에 의해 구현될 수 있다. FIG. 1 is a block diagram illustrating an
[0021] 비주얼 탐색 서버(14)는 TCP(transmission control protocol) 접속의 형태로 통상적으로 접속들을 수락하는 서버 디바이스를 표현하고 질의 데이터를 수신하고 식별 데이터를 제공하는 근거가 되는 TCP 세션을 형성하도록 그의 자신의 TCP 접속에 응답한다. 비주얼 탐색 서버(14)는 하나 이상의 기준 영상들 내의 하나 이상의 특징들 또는 객체들을 식별하기 위해 로컬 특징-기반 비주얼 탐색 알고리즘을 수행하거나 다른 방식으로 구현한다는 점에서, 비주얼 탐색 서버(14)는 비주얼 탐색 서버 디바이스를 표현할 수 있다. The visual search server 14 typically represents a server device that accepts connections in the form of a transmission control protocol (TCP) connection and establishes a TCP session upon which it receives a query data and provides identification data. Respond to its own TCP connection. The visual search server 14 performs or otherwise implements a local feature-based visual search algorithm to identify one or more features or objects in one or more reference images. Represents a server device.
[0022] 네트워크(16)는 인터넷과 같이, 클라이언트 디바이스(12)와 비주얼 탐색 서버(14)를 상호접속하는 공개 네트워크를 표현하지만, 네트워크(16)는 또한 사설 네트워크일 수 있다. 흔히, 네트워크(16)는 클라이언트 디바이스(12)와 비주얼 탐색 서버(14) 간에 데이터 또는 통신의 전달을 용이하게 하기 위한 OSI(open system interconnection) 모델의 다양한 층들을 구현한다. 네트워크(16)는 통상적으로 클라이언트 디바이스(12)와 비주얼 탐색 서버(14) 간에 데이터의 전달을 가능하게 하기 위해 스위치들, 허브들, 라우터들, 서버들과 같은 임의의 수의 네트워크 디바이스들을 포함한다. 단일의 네트워크로서 도시되지만, 네트워크(16)는 네트워크(16)를 형성하기 위해 상호접속되는 하나 이상의 서브-네트워크들을 포함할 수 있다. 이들 서브-네트워크들은 서비스 제공자 네트워크들, 액세스 네트워크들, 백엔드 네트워크들 또는 네트워크(16) 전체에 걸쳐서 데이터의 전달을 제공하기 위해 공개 네트워크에서 흔히 이용되는 임의의 다른 타입의 네트워크를 포함할 수 있다. 이 예에서 공개 네트워크로서 기술되지만, 네트워크(16)는 대중에 의해 일반적으로 액세스 가능하지 않은 사설 네트워크를 포함할 수 있다.
[0023] 도 1의 예에서 도시된 바와 같이, 클라이언트 디바이스(12)는 특징 추출 유닛(18), 특징 압축 유닛(20), 인터페이스(22) 및 디스플레이(24)를 포함한다. 특징 추출 유닛(18)은 스케일 불변 특징 변형 알고리즘 또는 특징들의 추출을 제공하는 임의의 다른 특징 기술 추출 알고리즘과 같은 특징 추출 알고리즘에 따라 특징 추출을 수행하는 유닛을 표현한다. 일반적으로, 특징 추출 유닛(18)은 클라이언트 디바이스(12) 내에 포함되는 카메라 또는 다른 영상 캡처 디바이스(도 1의 예에서 도시되지 않음)를 이용하여 로컬적으로 캡처될 수 있는 영상 데이터(26) 상에서 동작한다. 대안적으로 클라이언트 디바이스(12)는 국부적으로 다른 컴퓨팅 디바이스와의 유선 접속을 통해 또는 통신의 임의의 다른 유성 또는 무성 형태를 통해 네트워크(16)로부터 이러한 영상 데이터(26)를 다운로딩함으로써 그 영상 데이터를 스스로 캡처하지 않고 영상 데이터(26)를 저장할 수 있다. As shown in the example of FIG. 1, the client device 12 includes a
[0024] 아래에서 보다 상세히 기술되지만, 특징 추출 유닛(18)은 요약하면, 2개의 연속적인 가우시안-블러링된 영상들(Gaussian-blurred images)을 생성하기 위해 영상 데이터(26)를 가우시안 블러링함으로써 특징 기술자(28)를 추출할 수 있다. 가우시안 블러링은 일반적으로 정의된 스케일에서 가우시안 블러 함수로 영상 데이터(26)를 컨볼브(convolve)하는 것을 포함한다. 특징 추출 유닛(18)은 영상 데이터(26)를 증분적으로 컨볼브할 수 있고, 여기서 결과적인 가우시안-블러링된 영상들은 스케일 공간에서 상수만큼 서로로부터 분리된다. 특징 추출 유닛(18)은 "가우시안 피라미드" 또는 "가우시안 피라미드의 차이"로서 지칭될 수 있는 것을 형성하도록 이들 가우시안-블러링된 영상들을 적층(stack)할 수 있다. 특징 추출 유닛(18)은 DoG(difference of Gaussian) 영상들을 생성하도록 2개의 연속적으로 적층된 가우시안-블러링된 영상들을 비교한다. DoG 영상들은 "DoG 공간"으로서 지칭되는 것을 형성할 수 있다. Although described in more detail below,
[0025] 이러한 DoG 공간에 기초하여 특징 추출 유닛(18)은 키포인트(keypoint)들을 검출하며, 여기서 키포인트는 잠재적으로 지오메트리 관점에서 흥미로운 영상 데이터(26) 내의 특정한 샘플 지점 또는 픽셀 주위의 영역 또는 픽셀들의 패치(patch)를 지칭한다. 일반적으로 특징 추출 유닛(18)은 구성된 DoG 공간에서 로컬 최대 및/또는 로컬 최소로서 키포인트들을 식별한다. 특징 추출 유닛(18)은 이어서 키포인트가 검출된 패치에 대한 로컬 영상 그라디언트의 방향에 기초하여 하나 이상의 방위들, 또는 방향들을 이들 키포인트들에 할당한다. 이들 방위들을 특성화하기 위해, 특징 추출 유닛(18)은 그라디언트 방위 히스토그램(gradient orientation histogram)들의 견지에서 방위를 결정할 수 있다. 특징 추출 유닛(18)은 이어서 위치 및 방위(예를 들어, 그라디언트 방위 히스토그램에 의해)으로서 특징 기술자(28)를 정의한다. 특징 기술자(28)를 정의한 이후, 특징 추출 유닛(18)은 이 특징 기술자(28)를 특징 압축 유닛(20)에 출력한다. 통상적으로, 특징 추출 유닛(18)은 이러한 프로세스를 이용하여 특징 기술자들(28)의 세트를 특징 압축 유닛(20)에 출력한다.Based on this DoG space,
[0026]특징 압축 유닛(20)은 이들 특징 기술자들을 정의하기 위해 특징 추출 유닛(18)에 의해 이용된 데이터의 양에 대해, 특징 기술자들(28)과 같은 특징 기술자들을 정의하는데 이용되는 데이터의 양을 압축하거나 또는 다른 방식으로 감소시키는 유닛을 표현한다. 특징 기술자들(28)을 압축하기 위해, 특징 압축 유닛(20)은 특징 기술자들(28)을 압축하기 위해 타입 양자화(type quantization)로서 지칭되는 양자화의 형태를 수행할 수 있다. 이것에 관하여, 특징 기술자들(28)에 의해 정의된 히스토그램 그 전체를 송신하기 보단 오히려, 특징 압축 유닛(20)은 이른바 "타입"으로서 히스토그램을 표현하도록 타입 양자화를 수행한다. 일반적으로 타입은 히스토그램의 압축된 표현이다(예를 들어, 타입이 전체 히스토그램 보단 히스토그램의 형상을 표현하는 경우). 타입은 일반적으로 심볼들의 주파수들의 세트를 표현하고, 히스토그램의 맥락에서, 히스토그램의 그라디언트 분포의 주파수를 표현할 수 있다. 즉, 타입은 특징 기술자(28)의 대응하는 것을 생성한 소스의 진정한 분포의 추정을 표현한다. 이것에 관하여, 타입의 인코딩 및 전송은 분포의 형상을 인코딩하고 전송하는 것과 등가인 것으로 간주될 수 있는데, 그 이유는 그것이 특정한 샘플에 기초한 추정일 수 있기 때문이다(즉, 이 예에서 특징 기술자들(28)의 대응하는 것에 의해 정의된 히스토그램임). The
[0027] 특징 기술자들(28) 및 양자화의 레벨(" n"으로서 여기서 수학적으로 표시될 수 있음)이 정해지면, 특징 압축 유닛(20)은 특징 기술자들(28) 각각에 대해 파라미터들(k1, ..., km)(여기서 m은 치수들의 수를 표시함)을 갖는 타입을 컴퓨팅한다. 각각의 타입은 정해진 공통 분모를 갖는 유리수들의 세트를 표현하며, 여기서 유리수들은 1로 합산된다. 특징 기술자들(28)은 이어서 사전 편찬상 열거(lexicographic enumeration)를 이용한 인덱스로서 이러한 타입을 인코딩할 수 있다. 즉, 정해진 공통 분모를 갖는 모든 가능한 타입들에 대해, 특징 압출 유닛(20)은 이러한 타입들의 사전 편찬상의 순서에 기초하여 이들 타입들 각각에 인덱스를 효율적으로 할당한다. 특징 압출 유닛(20)은 그에 의해 단일의 사전 편찬상으로 배열된 인덱스들로 특징 기술자들(28)을 압축하고 질의 데이터(30)의 형태의 이들 압축된 특징 기술자들을 인터페이스(22)에 출력한다. Once the
[0028] 인터페이스(22)는 무선 네트워크 및 유선 네트워크를 포함하는 네트워크(16)를 통해 비주얼 탐색 서버(14)와 통신할 수 있는 임의의 타입의 인터페이스를 표현한다. 인터페이스(22)는 무선 셀룰러 인터페이스를 표현하고 비주얼 탐색 서버(14)와 네트워크(16)를 통해 그리고 네트워크(16)와 무선 셀룰러 네트워크를 통해 통신하기 위해, 필수 하드웨어 또는 안테나, 변조기들 등과 같은 다른 컴포넌트들을 포함할 수 있다. 이 예에서, 도 1의 예에서 도시되진 않았지만, 네트워크(16)는 무선 셀룰러 인터페이스(22)가 네트워크(16)와 통신하는 무선 셀룰러 액세스 네트워크를 포함한다. 디스플레이(24)는 영상 데이터(26), 또는 임의의 다른 타입들의 데이터와 같이 영상들을 디스플레이할 수 있는 임의의 타입의 디스플레이 유닛을 표현한다. 디스플레이(24)는 예를 들어, LED(light emitting diode) 디스플레이 디바이스, OLED(organic LED) 디스플레이 디바이스, LCD(liquid crystal display) 디바이스, 플라즈마 디스플레이 디바이스 또는 임의의 다른 타입의 디스플레이 디바이스를 표현할 수 있다. The
[0029] 비주얼 탐색 서버(14)는 인터페이스(32), 특징 재구성 유닛(34), 특징 매칭 유닛(36) 및 특징 기술자 데이터베이스(38)를 포함한다. 비주얼 탐색 서버(14)의 인터페이스(32)는 인터페이스(32)가 네트워크(16)와 같은 네트워크와 통신할 수 있는 임의의 타입의 인터페이스를 표현할 수 있다는 점에서 클라이언트 디바이스(12)의 인터페이스(22)와 유사하다. 특징 재구성 유닛(34)은 압축된 특징 기술자들로부터 특징 기술자들을 재구성하기 위해 압축된 특징 기술자들을 압축해제하는 유닛을 표현한다. 압축 재구성 유닛(34)은 압축된 특징 기술자들로부터 특징 기술자들을 재구성하기 위해 특징 재구성 유닛(34)이 양자화의 역(종종 재구성으로서 지칭됨)을 수행한다는 점에서 특징 압축 유닛(20)에 의해 수행된 동작들에 역으로 동작들을 수행할 수 있다. The visual search server 14 includes an
[0030] 특징 매칭 유닛(36)은 재구성된 특징 기술자들에 기초하여 영상 데이터(26)에서 하나 이상의 특징들 또는 객체들을 식별하기 위해 특징 매칭을 수행하는 유닛을 표현한다. 특징 매칭 유닛(36)은 이 특징 식별을 수행하기 위해 특징 기술자 데이터베이스(38)에 액세스할 수 있으며, 여기서 특징 기술자 데이터베이스(38)는 특징 기술자들을 정의하고 영상 데이터(26)로부터 추출된 대응하는 특징 또는 객체를 포함하는 기준 영상들에 이 특징 기술자들 중 적어도 일부를 연관시키는 데이터를 저장한다. 이들 기준 영상들은 또한 기준 영상들의 하나 이상의 주제들, 특징들 또는 객체들을 식별하는 식별 데이터와 연관될 수 있다. 데이터베이스(38)는 압축된 k-차원 트리(KD 트리)를 이용하여 이 데이터를 저장할 수 있다. The
[0031] 재구성된 특징 기술자들(이 데이터는 비주얼 탐색 또는 질의를 수행하는데 이용되는 비주얼 탐색 질의 데이터를 표현한다는 점에서 "질의 데이터 40"으로서 여기서 또한 지칭될 수 있음)에 기초하여 영상 데이터(26)로부터 추출된 특징 또는 객체를 성공적으로 식별하면, 특징 매칭 유닛(36)은 질의 결과 데이터(42)로서 하나 이상의 매칭 기준 영상들 및 임의의 연관된 식별 데이터를 리턴한다. [0031]
[0032] 초기에, 클라이언트 디바이스(12)의 사용자는 비주얼 탐색들 시작하기 위해 클라이언트 디바이스(12)와 상호작용한다. 사용자는 질의 영상 데이터(26)를 선택하기 위해 디스플레이(24)에 의해 제시되는 사용자 인터페이스 또는 다른 타입의 인터페이스와 상호작용하고 이어서 질의 영상 데이터(26)로서 저장된 영상의 포커스인 하나 이상의 특징들 또는 객체들을 식별하기 위해 비주얼 탐색을 개시할 수 있다. 예를 들어, 질의 영상 데이터(26)는 피사의 사탑과 같은 랜드마크의 영상을 특정할 수 있다. 사용자는 클라이언트 디바이스(12)의 영상 캡처 유닛(예를 들어, 카메라)을 이용하여 이 영상을 캡처하거나, 또는 대안적으로 네트워크(16)로부터 또는 다른 컴퓨팅 디바이스와의 유선 또는 무선 접속을 통해 로컬적으로 영상을 다운로드할 수 있다. 임의의 이벤트 시에, 질의 영상 데이터(26)를 선택한 이후, 사용자는 이 예에서, 랜드마크를 식별하기 위한 비주얼 탐색을 개시한다. Initially, a user of client device 12 interacts with client device 12 to begin visual searches. The user interacts with the user interface or other type of interface presented by
[0033] 비주얼 탐색의 개시에 응답하여, 클라이언트 디바이스(12)는 적어도 하나의 특징 기술자(28) 및 통상적으로 질의 영상 데이터(26)의 분석을 통해 발견된 이른바 "키포인트들" 중 하나를 기술하는 다수의 특징 기술자들(28)을 추출하기 위해 특징 추출 유닛(18)을 시동(invoke)한다. 특징 추출 유닛(18)은 이 질의 특징 기술자(28)를, 질의 특징 기술자(28)를 압축하고 질의 데이터(30)를 생성하도록 진행하는 특징 압축 유닛(20)에 포워딩한다. 특징 압축 유닛(2)은 네트워크(16)를 통해 비주얼 탐색 서버(14)에 질의 데이터(30)를 포워딩하는 인터페이스(22)에 질의 데이터(30)를 출력한다. In response to the initiation of the visual search, the client device 12 describes one of the so-called “keypoints” found through the analysis of at least one
[0034] 비주얼 탐색 서버(14)의 인터페이스(32)는 질의 데이터(30)를 수신한다. 질의 데이터(30)의 수신에 응답하여, 비주얼 탐색 서버(14)는 특징 재구성 유닛(34)을 시동한다. 특징 재구성 유닛(34)은 질의 데이터(30)에 기초하여 질의 특징 기술자(28)를 재구성하고 재구성된 특징 기술자들(40)을 출력한다. 특징 매칭 유닛(36)은 재구성된 질의 특징 기술자들(30)을 수신하고 질의 특징 기술자들(40)에 기초하여 특징 매칭을 수행한다. 특징 매칭 유닛(36)은 질의 특징 기술자들(40) 각각에 대해, 특징 기술자 데이터베이스(38)를 액세스하고 실질적으로 매칭 특징 기술자를 식별하기 위해 특징 기술자 데이터베이스(38)에 의해 데이터로서 저장된 기준 특징 기술자들을 트래버싱(traversing)함으로써 특징 매칭을 수행한다. 재구성된 질의 특징 기술자들(40)에 기초하여 영상 데이터(26)로부터 추출된 특징을 성공적으로 식별하면, 특징 매칭 유닛(36)은 질의 결과 데이터(42)로서 매칭 기준 특징 기술자들과 연관된 하나 이상의 매칭 기준 영상들 및 임의의 연관된 식별 데이터를 출력한다. 인터페이스(32)는 이러한 질의 결과 데이터(42)를 수신하고 네트워크(16)를 통해 클라이언트 디바이스(12)에 질의 결과 데이터(42)를 포워딩한다. The
[0035] 클라이언트 디바이스(12)의 인터페이스(22)는 이 질의 결과 데이터(42)를 수신하고 일반적으로 탐색 질의를 시동한 모든 애플리케이션에 이 질의 결과 데이터(42)를 포워딩한다. 즉, 클라이언트 디바이스(12)는 통상적으로 비주얼 탐색을 시동하고 질의 결과 데이터(42)와 같은 리턴된 질의 결과 데이터의 제시(presentation)를 관리할 수 있는 하나 이상의 애플리케이션들을 실행한다. 이 애플리케이션은 질의 결과 데이터(42)를 제시하도록 디스플레이(24)와 인터페이스할 수 있다. 몇몇 인터페이스들에서, 애플리케이션은 질의 결과 데이터(42)를 증가시키기 위해 질의 결과 데이터(42)에 의해 정의된 식별 데이터에 기초하여 부가적인 정보를 리트리브(retrieve)하도록 인터넷 탐색 또는 다른 동작들을 수행할 수 있다. 이 인스턴스에서, 질의 결과 데이터(42)의 식별 데이터는 랜드마크의 명칭, 즉, 이 예에서, 피사의 사탑, 피사의 사탑을 건설한 건설자의 명칭, 피사의 사탑의 완성 데이터, 및 이 랜드마크와 관련된 임의의 다른 정보를 포함할 수 있다. The
[0036] 비주얼 탐색이 제한된 입력 매커니즘들(이를 테면, 사용자에 의한 텍스트의 입력을 제한하거나 좌절시킬 수 있는 햅틱 피드백(haptic feedback)을 거의 제공하지 않는 가상 키보드) 및/또는 더 작은 스크린들을 갖는 클라이언트 디바이스들과의 사용자 상호작용을 용이하게 하고 다양한 애플리케이션들을 용이하게 하는 견지에서 다수의 이점들을 제공할 수 있지만, 몇몇 인스턴스들에서, SIFT(scale invariant feature transform) 알고리즘과 같은 몇몇 비주얼 탐색 알고리즘들은 특징 매칭의 수행의 견지에서 부족할 수 있다. 이들 부족들을 예시하기 위해 SIFT 알고리즘은 빌딩(예를 들어, 피사의 사탑)에 걸쳐서 반복되는 특유의 아치들 또는 창문들과 같이 탐색 및 기준 영상들의 반복 특징들로부터 질의 특징 기술자 및 기준 특징 기술자들 각각이 추출될 때, 그렇지 않았다면 인스턴스들에서 탐색 또는 질의 특징 기술자에 매칭했었을 기준 특징 기술자를 폐기할 수 있다. 또한, SIFT 알고리즘은 흔히 임의의 정해진 비주얼 탐색에 응답하여 단일의 영상만을 리턴하며, 여기서 이 리턴된 영상은 SIFT 알고리즘에 의해 알고리즘적으로 "최상의 매칭"인 것으로 결정된다. 그러나 사용자들은 무엇이 SIFT 알고리즘과 동일한 방식으로 "최상의 매칭"를 구성할지 결정할 수 없을 수 있고, 이는 단일의 SIFT 최상의 매칭 결과가 사용자의 기대들에 매칭하지 않을 수 있기 때문에 사용자의 좌절을 초래할 수 있다. [0036] Client with visual navigation limited input mechanisms (such as a virtual keyboard that provides little or no haptic feedback that can limit or frustrate input of text by a user) and / or a client with smaller screens While it may provide a number of advantages in terms of facilitating user interaction with devices and facilitating a variety of applications, in some instances, some visual search algorithms, such as scale invariant feature transform (SIFT) algorithms, may feature match. May be lacking in terms of the performance of To illustrate these deficiencies, the SIFT algorithm uses query feature descriptors and reference feature descriptors, respectively, from repetitive features of search and reference images, such as unique arches or windows that are repeated across a building (eg, the Leaning Tower of Pisa). When this is extracted, it may discard the reference feature descriptor that would otherwise have matched the search or query feature descriptor in the instances. In addition, the SIFT algorithm often returns only a single image in response to any given visual search, where the returned image is determined to be "best match" algorithmically by the SIFT algorithm. However, users may not be able to determine what constitutes "best match" in the same way as the SIFT algorithm, which may cause user frustration because a single SIFT best matching result may not match the user's expectations.
[0037] 보다 구체적으로, SIFT 알고리즘을 포함하는 비주얼 탐색 알고리즘들 "유사성 측정(similarity measure)"으로서 지칭될 수 있는 것을 이용하여 특징 매칭을 구현할 수 있다. SIFT 알고리즘은 기준 특징 기술자들의 각각에 대해 질의 특징 기술자가 얼마나 유사한지를 특정하기 위해 거리 비 테스트(distance ratio test)를 이용한다. 이 거리 비는 질의 특징 기술자들의 현재의 것의 최근접 기준 특징 기술자가 질의 특징 기술자들의 현재의 것의 제 2 최근접(특징 기술자 공간에서) 특징 기술자에 대해 얼마나 멀리(재차 특징 기술자 공간에서) 있는지를 측정한다. 최근접 및 제 2 최근접 기준 특징 기술자가 매우 근접(임계치에 의해 식별된 바와 같이)한 경우, SIFT 알고리즘은 질의 특징 기술자의 현재의 것이 고유하지 않고 그에 따라 매칭이 신뢰할 수 있지 않다고 결정한다. 거리 비 유사성 측정은 다음의 수학식(1)에 의해 표현될 수 있다. More specifically, feature matching may be implemented using what may be referred to as visual search algorithms “similarity measure” including a SIFT algorithm. The SIFT algorithm uses a distance ratio test to specify how similar the query feature descriptors are to each of the reference feature descriptors. This distance ratio measures how far (in the feature descriptor space) the nearest reference feature descriptor of the current feature of the query feature descriptors with respect to the second nearest (in the feature descriptor space) feature of the query feature descriptors' current one. do. If the nearest and second nearest reference feature descriptors are very close (as identified by the threshold), the SIFT algorithm determines that the current of the query feature descriptor is not unique and therefore the matching is not reliable. The distance dissimilarity measurement can be expressed by the following equation (1).
수학식(1)에서, q는 질의 기술자를 표현하고, nn1은 데이터베이스 내의 최근접 기준 특징 기술자("가장 근처의 이웃(nearest neighbor)" 또는 "nn")으로서 또한 지칭될 수 있음)를 표현하고, nn2는 데이터베이스 내의 제 2 최근접 기준 특징 기술자("제 2 가장 근처의 이웃"으로서 지칭될 수 있음)를 표현하고, d는 놈 연산(norm operation)을 표현하고, T는 임계치를 표현한다. In equation (1), q represents the query descriptor and nn 1 represents the nearest reference feature descriptor (which may also be referred to as "nearest neighbor" or "nn") in the database. Nn 2 represents a second nearest reference feature descriptor (which may be referred to as a “second closest neighbor”) in the database, d represents a norm operation, and T represents a threshold do.
[0038] SIFT 거리 비 유사성 측정이 통상적으로 적합한 결과들을 제공하지만, SIFT 거리 비 유사성 측정은 특정한 인스턴스들에서 매칭 기준 특징 기술자를 올바르게 식별하는데 실패할 수 있다. 예를 들어, 영상이 반복 구조들(이를 테면, 도 7의 예에서 도시된 피사의 사탑의 반복되는 창문 구조들)을 포함하는 인스턴스들에서, SIFT 거리 비 유사성 측정은 그의 2개의 최근접 기준 특징 기술자들(피사의 사탑을 도시하는 영상 데이터로부터 또한 추출됨)간의 거리가 작을 수 있다는 것을 고려하면, 이러한 반복되는 영상 특징들로부터 추출된 질의 특징 기술자들이 고유하지 않다고 결정할 수 있다. 이 인스턴스에서, SIFT 거리 비 유사성 측정은 잠재적으로 올바른 매칭을 거절할 수 있다. Although the SIFT distance dissimilarity measure typically provides suitable results, the SIFT distance dissimilarity measure may fail to correctly identify the matching criteria feature descriptor in certain instances. For example, in instances where the image includes repeating structures (such as repeating window structures of the Leaning Tower of Pisa shown in the example of FIG. 7), the SIFT distance dissimilarity measure is characterized by its two nearest reference features. Given that the distance between the descriptors (also extracted from the image data showing the Leaning Tower of Pisa) may be small, one may determine that the query feature descriptors extracted from these repeated image features are not unique. In this instance, the SIFT distance dissimilarity measure can potentially reject correct matching.
[0039] 본 개시에서 기술된 기법들에 따라, 비주얼 탐색 서버(14)의 특징 매칭 유닛(36)은 반복 구조들을 수용하고 이들 및 다른 인스턴스들에서 모다 정확한 매칭을 다른 방식으로 용이하게 하는 더 많은 강건한 거리 비 유사성 측정을 이용한다. 또한, 기법들은 종래의 시스템들에서 공통적인 바와 같이 단일의 "최상의 매칭" 기준 영상을 단순히 리턴하기 보다는 오히려 "최상의 매칭"의 사용자 지각 및 알고리즘식 결정에서의 차이들을 수용하도록 기준 영상들의 순서화된 랭킹(ordered ranking)을 제공할 수 있다. In accordance with the techniques described in this disclosure, the
[0040] 본 개시에서 기술된 기법들에 따라 거리 비 유사성 측정을 구현하는데 있어서, 특징 매칭 유닛(36)은 재구성된 질의 특징 기술자들(40) 중 하나와 특징 기술자 데이터베이스(38)에 저장된 복수의 기준 특징 기술자들 각각 간의 거리를 우선 컴퓨팅할 수 있다. 특징 매칭 유닛(36)은 이어서 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 클러스터링 알고리즘(clustering algorithm)을 이용하여 결정할 수 있다. 공통적은 클러스터링 알고리즘들은 k-평균 클러스터링 알고리즘(여기서 k는 이 예에서 제 1 및 제 2 그룹들을 생성하기 위해 2로 세팅됨), 가우시안 필터링 알고리즘 및 그래픽 컷팅 알고리즘을 포함할 수 있다. In implementing the distance dissimilarity measurement in accordance with the techniques described in this disclosure, the
[0041] 몇몇 인스턴스들에서, 클러스터링 알고리즘은 가증 근처의 또는 최소 거리를 제 1 그룹으로 그리고 복수의 다음의 가장 근처의 또는 최소 거리들을 제 2 그룹으로 클러스터링하는 알고리즘을 포함할 수 있으며, 여기서 제 2 그룹의 복수의 다음의 가장 근처의 또는 최소 거리들의 수는 예를 들어, 2, 3, 또는 4개의 다음의 가장 근처의 거리들을 포함할 수 있다. k-평균 클러스터링 알고리즘과 같은 보다 형식적인 클러스터링 알고리즘들에 관하여 여기서 기술되지만, 2개 의상의 그룹들(여기서 제 1 그룹은 하나 이상의 거리들을 포함하고 제 2 그룹은 2개 이상의 거리들을 포함함)을 결정하는 임의의 알고리즘은 본 개시에서 기술되는 기법들에 관하여 활용될 수 있다. In some instances, the clustering algorithm may include an algorithm that clusters the near or minimal distance into the first group and the plurality of next nearest or minimum distances into the second group, wherein the second The number of the plurality of next nearest or minimum distances of the group may include, for example, two, three, or four next nearest distances. More formal clustering algorithms, such as the k-means clustering algorithm, are described herein, but include two groups of clothing, where the first group contains one or more distances and the second group contains two or more distances. Any algorithm that determines may be utilized with respect to the techniques described in this disclosure.
[0042] 클러스터링 알고리즘을 이용하면, 특징 매칭 유닛(36)은 컴퓨팅된 거리들 중 2개 의상의 제 1 그룹을 결정할 수 있어서, 제 1 그룹은 특징 기술자 데이터베이스(38)에 저장된 복수의 기준 특징 기술자들 중 연관된 하나가 컴퓨팅된 거리들 의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 관하여 질의 특징 기술자에 대해 근처에 있게 된다. 또한, 이 클러스터링 알고리즘을 이용하면, 특징 매칭 유닛(36)은 컴퓨팅된 차이들의 제 2 그룹을 결정할 수 있어서, 이러한 제 2 그룹은 특징 기술자 데이터베이스(38)에 저장된 복수의 기준 특징 기술자들 중 연관된 하나가 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 관하여 질의 특징 기술자들(30) 중 현재의 것으로부터 떨어져 있게 된다. Using the clustering algorithm, the
[0043] 비주얼 탐색 서버(14)의 특징 매칭 유닛(36)은 이어서 질의 특징 기술자들(40) 중 현재의 것이 컴퓨팅된 거리들의 결정된 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹에 기초하여 컴퓨팅된 거리들의 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정할 수 있다. 예를 들어, 특징 매칭 유닛(36)은 제 1 그룹 거리 평균을 생성하기 위해 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 평균을 우선 컴퓨팅하고, 마찬가지로 제 2 그룹 거리 평균을 생성하기 위해 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 평균을 컴퓨팅할 수 있다. 제 1 및 제 2 그룹 거리 평균들의 컴퓨팅 시에, 특징 매칭 유닛(36)은 평균 거리 비 측정을 생성하기 위해 제 2 그룹 거리 평균으로 제 1 그룹 거리 평균을 나눌 수 있다. 특징 매칭 유닛(36)은 다음으로 임계값에 평균 거리 비 측정을 비교하고 비교에 기초하여 질의 특징 기술자들(40)의 현재의 것이 컴퓨팅된 거리들 중 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정할 수 있다. The
[0044] 이러한 방식으로 컴퓨팅된 거리들을 클러스터링하거나 다른 방식으로 그룹핑하고 이어서 각각의 그룹의 거리들을 평균화함으로써, 기법들은 서로 근처에 있고 양자가 판에 박은 듯이 공통적인(common conventionally) 바와 같이 질의 특징 기술자에 매칭하는 임의의 기준 특징 기술자들을 완전히 거절함 없이 가까운 반복 특징들로부터 추출된 특징 기술자들의 매칭을 수용할 수 있다. 클러스터링 알고리즘을 이용하는 거리 측정들의 그룹핑은 또한 근처의 또는 멀리 있는 특징 기술자들 간의 더 명확한 판별을 달성할 수 있어서, 비주얼 탐색 서버(14)의 특징 매칭 유닛(36)은 거리를 이용하여 서로로부터 특유의 또는 고유한 특징 기술자들을 올바르게 식별할 수 있다. 거리 측정들을 평균화함으로써, 특징 매칭 유닛(36)은 임계치를 올바르게 적용하고 그에 의해 매칭 기준 특징 기술자로 고려되는 것의 거절을 방지하도록 이들 2개의 그룹들이 서로로부터 얼마나 멀리 떨어져 있는지에 관한 상대적 근접 근사를 제공할 수 있다. By clustering or otherwise grouping the distances computed in this manner and then averaging the distances of each group, the techniques are in the vicinity of each other and the query feature descriptor as common conventionally as if both are plated. It is possible to accept a match of feature descriptors extracted from nearby repeating features without completely rejecting any reference feature descriptors that match. Grouping of distance measurements using a clustering algorithm can also achieve a clearer distinction between nearby or distant feature descriptors, such that
[0045] 기법들의 매칭 영상 양상들의 순서화된 또는 랭크된 리스트를 구현하기 위해 비주얼 탐색 서버(14)의 특징 매칭 유닛(36)은 컴퓨팅된 거리들의 제 2 그룹에 비교하여 질의 특징 기술자들(40)의 현재의 것에 비교적 근처에 있는 컴퓨팅된 거리들의 제 1 그룹들을 활용한다. 위에서 기술된 보다 강건한 거리 유사성 측정을 이용하여 매칭하는 것으로 결정되고 제 1 그룹에 있는 것으로 결정된 모든 컴퓨팅된 거리들에 대해, 특징 매칭 유닛(36)은 제 1 그룹의 컴퓨팅된 거리들에 대응하는 매칭 기준 특징 기술자들과 연관되는 특유의 영상들에 보트(vote)를 할당할 수 있다. 즉, 제 1 그룹의 컴퓨팅된 거리들에 대응하는 기준 특징 기술자들의 다수의 것들이 동일한 기준 영상으로부터 추출되는 경우, 특징 매칭 유닛(36)은 단일의 보트를 그 기준 영상에 할당한다. To implement an ordered or ranked list of matching image aspects of the techniques,
[0046] 예를 들어, 특징 매칭 유닛(36)은 기준 영상들의 그룹이 어떤 복제 기준 영상들도 포함하지 않도록 고유한 기준 영상들의 그룹을 결정할 수 있다. 특징 매칭 유닛(36)은 제 1 그룹에 있는 것으로 결정된 컴퓨팅된 거리들이 컴퓨팅된 기준 특징 기술자들을 먼저 고려할 수 있으며, 여기서 이들 기준 특징 기술자들은 "제 1 그룹 기준 특징 기술자들"로서 지칭될 수 있다. 각각의 기준 특징 기술자는 특징 기술자 데이터베이스(38)를 초기에 구축할 때 그 기준 특징 기술자가 추출된 기준 영상(특징 기술자 데이터베이스(38) 또는 도 1의 예에서 도시되지 않은 몇몇 다른 데이터베이스, 메모리 또는 저장 유닛에 또한 저장될 수 있음)과 연관된다. 특징 매칭 유닛(36)은 이어서 제 1 그룹 기준 특징 기술자들과 연관된 그러한 기준 영상들로서 기준 영상들의 제 1 그룹을 결정할 수 있다. 특징 매칭 유닛(36)은 이어서 기준 영상들의 그룹이 어떠한 복제 기준 영상들도 포함하지 않도록 고유한 기준 영상들의 그룹을 생성하기 위해 기준 영상들이 초기 그룹으로부터 임의의 복제 기준 영상들을 제거할 수 있다. For example, feature matching
[0047] 특징 매칭 유닛(36)은 이어서 고유한 기준 영상들의 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당할 수 있다. 보트는 1과 같은 상수일 수 있다. 대안적으로 보트는 최근접 기준 특징 기술자 및 질의 특징 기술자들(40) 중 현재의 것 간의 컴퓨팅된 거리에 비견되는 현재의 컴퓨팅된 거리의 거리 비에 비례할 수 있다. 다른 대안으로서, 보트는 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대까지 순서화될 때 제 1 그룹 내의 랭킹에 비례할 수 있다(예를 들어, 제 1 그룹 기준 특징 기술자들 중 하나가 질의 특징 기술자들(40)의 현재의 것에 5번째 최근접일 때, 보트는 1/5일 수 있음). 특징 매칭 유닛(36)은 이어서 질의 특징 기술자들(40) 각각에 대해 이러한 방식으로 보트들을 할당한다. 이러한 방식으로 기준 또는 타겟 영상들에 보트들이 할당된 이후, 특징 매칭 유닛(36)은 이어서 수집된 보트들에 기초하여 기준 또는 타겟 영상들을 랭크하고 질의 결과 데이터(42)의 형태로 질의 데이터(30)에 응답하여 타겟 영상들의 랭크 또는 순서화된 리스트를 제공할 수 있다. The
[0048] 다양한 컴포넌트들, 모듈들 또는 유닛들이 개시된 기법들을 수행하도록 구성된 디바이스들의 기능적 양상들을 강조하기 위해 본 개시에서 기술되지만, 이들 유닛들이 반드시 상이한 하드웨어 유닛들에 의한 실현을 요구하는 것은 아니다. 오히려, 다양한 유닛들은 하드웨어 유닛에서 조합되거나, 컴퓨터-판독 가능한 매체들에 저장된 적합한 소프트웨어 및/또는 펌웨어와 함께, 위에서 기술된 바와 같은 하나 이상의 프로세서들을 포함하는 상호-동작 가능한 하드웨어의 모음에 의해 제공될 수 있다. 이러한 것에 관하여, 본 개시들에서 유닛들에 대한 참조는 별개의 하드웨어 유닛들 및/또는 하드웨어 및 소프트웨어 유닛들로서 구현될 수 있거나 구현될 수 없는 상이한 기능적 유닛들을 제안하는 것으로 의도된다. 여기서 이용되는 바와 같은 구문 "컴퓨터 판독 가능한 매체"는 단지 제조물들에 적용되며 일시적인 전파 신호들에 적용되지 않는다. Although various components, modules, or units are described in this disclosure to emphasize functional aspects of devices configured to perform the disclosed techniques, these units do not necessarily require realization by different hardware units. Rather, the various units may be provided by a collection of inter-operable hardware, including one or more processors as described above, in combination with the hardware unit, or in combination with suitable software and / or firmware stored on computer-readable media. Can be. In this regard, reference to units in the present disclosures is intended to suggest different functional units that may or may not be implemented as separate hardware units and / or hardware and software units. The phrase “computer readable medium” as used herein applies only to articles of manufacture and not to transient propagation signals.
[0049] 도 2는 도 1의 예에서 도시된 특징 매칭 유닛(36)을 보다 상세히 예시하는 블록도이다. 도 2의 예에서, 특징 매칭 유닛(36)은 거리 컴퓨팅 유닛(distance computation unit; 50), 그룹핑 유닛(52), 매칭 유닛(54) 및 결과 생성기 유닛(56)을 포함한다. 거리 컴퓨팅 유닛(50)은 질의 특징 기술자들(40) 및 특징 기술자 데이터베이스(38)에 저장된 기준 특징 기술자들(51)에 기초하여 거리들(62A 내지 62N)("거리 62")을 컴퓨팅하는 유닛이다. 보다 구체적으로, 거리 컴퓨팅 유닛(50)은 질의 특징 기술자들(40) 중 현재의 것으로부터 기준 특징 기술자들(51) 각각을 차감한 절댓값으로서 질의 특징 기술자들(40) 각각에 대한 거리들(62)을 컴퓨팅하는 유닛을 표현할 수 있다. 거리 컴퓨팅 유닛(50)은 거리들(62)을 그룹핑 유닛(52)에 출력한다. FIG. 2 is a block diagram illustrating in more detail the
[0050] 그룹핑 유닛(52)은 거리들(62)과 같은 거리들 또는 2개의 상의 값들의 임의의 다른 비-엠티(non-empty) 세트를 수신하고 클러스터링 알고리즘(64)에 따라 이 값들을 적어도 2개의 그룹들로 그룹핑하는 유닛을 표현한다. 클러스터링 알고리즘(64)은 k-평균 클러스터링 알고리즘(여기서 k는 이 예에서 제 1 및 제 2 그룹들을 생성하기 위해 2로 세팅됨), 가우시안 필터링 알고리즘 및 그래픽 컷팅 알고리즘은 물론 값들의 세트로부터 적어도 2개의 그룹들을 생성할 수 있는 임의의다른 공통 클러스터링 알고리즘 중 하나 이상을 표현한다. 도 2의 예에서, 그룹핑 유닛(52)은 거리들(62)을 수신하고 클러스터링 알고리즘(64)에 따라 거리들(62) 중 상이한 것들의 그룹들(66A, 66B("그룹들(66)")을 컴퓨팅한다. 그룹핑 유닛(52)은 컴퓨팅된 거리들(62)의 2개 이상의 그룹(66a)을 결정할 수 있어서, 이 제 1 그룹(66A)은 특징 기술자 데이터베이스(38)에 저장된 기준 특징 기술자들(51) 중 연관된 하나가 컴퓨팅된 거리들(62)의 그룹(66B) 내에 있을 것으로 결정된 컴퓨팅된 거리들(62)의 것들에 관하여 질의 특징 기술자들(40)의 현재의 것에 대해 근처에 있음을 표시하는 컴퓨팅된 거리들(62)의 것들을 포함한다. 또한, 클러스터링 알고리즘(64)에 따라, 그룹핑 유닛(52)은 컴퓨팅된 거리들(62)의 그룹(66B)을 결정할 수 있어서, 이 제 2 그룹(66B)은 컴퓨팅된 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 관하여 질의 특징 기술자들(40)의 현재의 것으로부터 떨어져 있음을 표시하는 컴퓨팅된 거리들(62)의 것들을 포함한다. 그룹핑 유닛(52)은 거리들(62)의 그룹들(66)을 매칭 유닛(54)에 출력한다. Grouping unit 52 receives any other non-empty set of distances, such as
[0051] 매칭 유닛(54)은 질의 특징 기술자들(40) 중 하나 이상이 기준 특징 기술자들(51) 중 하나 이상에 고유하게 매칭하는지를 결정하는 유닛을 표현한다. 질의 특징 기술자들(40)의 현재의 것이 기준 특징 기술자들(51) 중 하나 이상에 고유하게 매칭하는지를 결정하기 위해, 매칭 유닛(54)은 통상적으로 제공된 그룹들 각각의 값들의 평균을 컴퓨팅한다. 도 2의 예에서, 매칭 유닛(54)은 그룹(66A)의 거리들(62) 및 그룹(66B)의 거리들(62)을 각각 평균화함으로써 그룹 평균(68A, 68B)을 컴퓨팅한다. 다음으로, 매칭 유닛(54)은 그룹 평균(68B)으로 그룹 평균(68A)을 나누고 결과를 임계치(70)에 비교한다. 즉, 매칭 유닛(54)은 일반적으로 클러스터링 알고리즘(64)을 이용하여 형성된 거리들(62)의 그룹들(66)로부터 컴퓨팅된 그룹 평균들에 대해서만 SIFT 알고리즘에 의해 현재 수행된(및 수학식(1)으로서 위에서 도시된) 것에 대한 유사한 비교를 수행한다. Matching unit 54 represents a unit that determines whether one or more of
[0052] 그룹 평균(68B)으로 그룹 평균(68A)을 나눈 결과가 임계치 보다 큰 경우(그룹(66B)과 연관된 기준 특징 기술자들(51)이 그룹(66A)과 연관된 것에 근접하다는 것을 의미함), 매칭 유닛(54)은 특징 기술자들(40) 중 현재의 것이 기준 특징 기술자들(51) 중 어느 것에도 고유하게 매칭하지 않는다는 것을 표시하는 매칭 표시자(72)를 출력한다. 용어 "고유한 매칭(unique match)"는 매칭이 존재하지만 질의 영상 데이터의 식별을 용이하게 할 수 없고 그에 따라 매칭이 고유한 것으로 간주되지 않는 비주얼 탐색을 수행하는 맥락에서의 특징 매칭의 양상들을 지칭하도록 여기서 이용된다. 매칭은 매칭이 질의 영상 데이터의 식별을 용이하게 하는 경우 고유하다. 예를 들어, 피사의 사탑 상의 아치들은 이 랜드마크를 고유하게 식별할 수 있는 질의 특징 기술자들로서 피사의 사탑의 질의 영상으로부터 추출될 수 있다. 피사의 사탑의 기준 영상에서 이러한 아치들로부터 추출된 기준 특징 기술자들은 매칭할 수 있다. 고유성의 좁은 정의 및 이들 아치들의 반복 성질을 고려하는 종래의 SIFT 알고리즘에서 공통적인 바와 같은 이들 매칭 기준 영상 특징 기술자들을 거절하기 보단 오히려, 매칭 유닛(54)은 매칭 유닛(54)이 동작하는 데이터의 클러스터링 성질로 인해 반복에도 불구하고 이들이 고유하게 매칭한다고 적절히 결정할 수 있다. 이 고유한 매칭은 위에서 기술된 유사성 측정으로서 또한 지칭될 수 있다. 고유한 매칭들은, 이들이 매칭 유닛(54)이 비-고유 매칭들을 거절하는 원인인 비-고유한 매칭들보다 더 빨리 질의 영상 데이터의 식별을 용이하게 하기 때문에 바람직하다. When the result of dividing the group average 68A by the group average 68B is greater than the threshold (meaning that the
[0053] 임의의 이벤트 시에, 그룹 평균(68B)으로 그룹 평균(68A)을 나눈 결과가 임계치 미만인 경우(그룹(66B)과 연관된 기준 특징 기술자들(51)이 그룹(66A)과 연관된 것들로부터 떨어져 있음을 의미함), 매칭 유닛(54)은 특징 기술자들(40)의 현재의 것이 거리들(62) 중 최소의 것과 연관되는 기준 특징 기술자들(51) 중 하나와 고유하게 매칭한다는 것을 표시하는 매칭 표시자(72)를 출력한다. 매칭 유닛(54)은 이 매칭 표시자(72)를 출력하고 그룹(66A)을 결과 생성기 유닛(56)으로 포워딩한다. 몇몇 인스턴스들에서, 매칭 유닛(54)은 매칭 유닛(54)이 어떠한 매칭도 존재하지 않는다고 결정할 때 결과 생성기 유닛(56)이 그룹(66A)을 고려할 필요가 없기 때문에, 매칭 표시자(72)가 매칭하는 경우에만 그룹(66A)을 포워딩한다. At any event, if the result of dividing the group average 68A by the group average 68B is below the threshold (the
[0054] 결과 생성기 유닛(56)은 질의 결과 데이터(42)를 생성하는 유닛을 표현한다. 결과 생성기 유닛(56)은 리스트 형성 유닛(58) 및 보트 할당 유닛(60)을 포함한다. 리스트 형성 유닛(58)은 그룹(66A)에 기초하여 고유한 기준 영상들(74)의 리스트를 형성하는 유닛을 표현한다. 보다 구체적으로, 리스트 형성 유닛(58)은 매칭 표시자(72)가 매칭을 시그널링할 때, 그룹(66A)의 거리들(62)이 컴퓨팅된 기준 특징 기술자들(51)의 것들을 결정하도록 그룹(66A)을 프로세싱할 수 있다. 리스트 생성 유닛(58)은 이어서 기준 특징 기술자들(51)의 이러한 것들 각각이 추출된 기준 영상들(53)을 리트리브하고 초기 기준 영상 리스트(76)를 형성한다. 리스트 형성 유닛(58)은 이어서 고유한 기준 영상 리스트(74)를 생성하기 위해 초기 기준 영상 리스트(76)로부터 임의의 중복 영상들을 제거할 수 있다.
[0055] 초기 기준 영상 리스트(76)를 형성하는 것으로서 기술되지만, 리스트 형성 유닛(58)은 이러한 리스트(76)를 반드시 형성할 필요는 있는 것이 아니라 대신 기준 영상들(53)의 고유한 것들 만을 리트리브할 수 있다. 즉, 리스트 형성 유닛(58)은 기준 특징 기술자들(51)의 결정된 것들이 추출된 기준 영상들(53)을 리트리브할 때, 먼저 그것이 이미 영상들(53)의 이러한 하나를 리트리브하였는지를 결정하고 이어서 그것이 영상들(53)의 이러한 하나를 이미 검색하지 않은 경우에만 영상들(53)의 이러한 하나를 리트리브할 수 있다. 영상들(53)의 사본 또는 복제들을 저장하는 것을 방지함으로써, 리스트 형성 유닛(58)은 메모리 소비를 방지할 수 있고, 이는 구현자가 메모리 요건들을 감소하는 것을 가능하게 할 수 있다. 이러한 이유로, 기법들은 고유한 기준 영상 리스트(74)를 컴퓨팅하는 임의의 하나의 방식으로 제한되어선 안 된다. 이로서, 리스트 형성 유닛(58)이 고유한 기준 영상 리스트(74)를 어떻게 컴퓨팅하는지에 무관하게, 리스트 형성 유닛(58)은 보트 할당 유닛(60)에 고유한 기준 영상 리스트(74)를 출력한다. Although described as forming the initial reference image list 76, the
[0056] 보트 할당 유닛(60)은 기준 영상들(53)의 하나 이상에 보트들을 할당하는 유닛을 표현한다. 통상적으로, 보트 할당 유닛(60)은 보트 집계 표(78) 내의 엔트리(entry)에 이들 영상들(53) 각각을 연관시킴으로써 고유한 기준 영상 리스트(74)에 의해 식별되는 영상들(53)에 보트들을 할당한다. 보트 할당 유닛(60)은 각각의 엔트리의 보트 카운트를 증가시키도록 영상들(53)과 연관된 각각의 엔트리를 업데이트할 수 있다. 보트 할당 유닛(60)은 위에서 기술된 방식들을 포함해서 임의의 수의 방식들로 보트들을 결정할 수 있다. 즉, 보트는 1과 같은 상수 값일 수 있다. 대안적으로, 보트는 최근접 기준 특징 기술자와 질의 특징 기술자들(40) 중 현재의 것 간의 컴퓨팅된 거리에 비견되는 현재의 컴퓨팅된 거리의 거리 비에 비례할 수 있다. 다른 대안으로서, 보트는 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대까지 순서화될 때 제 1 그룹 내의 랭킹에 비례할 수 있다(예를 들어, 제 1 그룹 기준 특징 기술자들 중 하나가 질의 특징 기술자들(40)의 현재의 것에 5번째 최근접일 때, 보트는 1/5일 수 있음).The
[0057] 거리 컴퓨팅 유닛(50), 그룹핑 유닛(52), 매칭 유닛(54), 및 결과 생성기 유닛(56)은 질의 특징 기술자들(40) 모두가 이 특징 매칭 프로세스를 경험할 때까지 위에서 기술된 방식으로 지속될 수 있다. 질의 특징 기술자들(40)의 마지막 것이 프로세싱된 후에, 결과 생성기 유닛(56)은 보트 집계 표(78)에 기초하여 질의 결과 데이터(42)를 구성한다. 예를 들어, 결과 생성기 유닛(56)은 임의의 제한 또는 임계치까지 최다 보트들, 제 2의 최다 보트들, 제 3의 최다 보트들 등을 수신한 기준 영상들(53)의 것들을 리트리브하고 이들 영상들(53)을 (특징 기술자 데이터베이스(38) 내의 이들 영상들 각각을 기술하거나 또는 다른 방식으로 연관되는 메타데이터 또는 다른 데이터에 따라) 질의 결과 데이터(42)로서 출력할 수 있다. 대안적으로, 결과 생성기 유닛(56)은 보트를 수신한 영상들(53) 중 임의의 것으로서 (재차, 특징 기술자 데이터베이스(38) 내의 이들 영상들 각각을 기술하거나 또는 다른 방식으로 연관되는 메타데이터 또는 다른 데이터에 따라) 질의 결과 데이터(42)를 형성할 수 있다.The
[0058] 도 3은 본 개시에서 기술되는 특징 매칭 기법들을 구현하는데 있어 도 1의 예에서 도시된 비주얼 탐색 서버(14)와 같은 비주얼 탐색 서버의 예시적인 동작을 예시하는 흐름도이다. 초기에, 비주얼 탐색 서버(14)는 통상적으로 압축된 특징 기술자들을 정의하는 질의 데이터(30)를 인터페이스(32)를 통해 수신한다(90). 비주얼 탐색 서버(14)의 특징 재구성 유닛(34)은 재구성된 특징 기술자들(40)을 생성하기 위해 질의 데이터(30)에 의해 정의된 압축된 특징 기술자들로부터 질의 특징 기술자들(38)을 재구성한다(92). 특징 재구성 유닛(34)은 특징 매칭 유닛(36)에 재구성된 질의 특징 기술자들(40)을 출력한다. FIG. 3 is a flowchart illustrating an example operation of a visual search server, such as the visual search server 14 shown in the example of FIG. 1, in implementing the feature matching techniques described in this disclosure. Initially, visual search server 14 typically receives 90
[0059] 특징 매칭 유닛(36)은 (도 2의 예에서 도시된 바와 같은) 거리 컴퓨팅 유닛(50)을 통해 이러한 질의 특징 기술자들(40)을 수신한다. 거리 컴퓨팅 유닛(50)은 질의 특징 기술자들(40) 중 하나를 선택한다(94). 거리 컴퓨팅 유닛(50)은 이어서 위에서 기술된 방식으로 특징 기술자 데이터베이스(38)에 저장된 기준 특징 기술자들(51) 중 하나 이상과 질의 특징 기술자들(40) 중 선택된 하나 간의 거리를 컴퓨팅한다(96). 이들 거리들은 거리들(62)로서 도 2의 예에서 도시된다. 거리 컴퓨팅 유닛(50)은 이들 거리들(62)을 그룹핑 유닛(52)에 출력한다.
[0060] 이들 거리들(62)을 수신 시에, 그룹핑 유닛(52)은 클러스터링 알고리즘(64)에 따라 컴퓨팅된 거리(62)의 제 1 및 제 2 그룹들(66A, 66B)을 결정한다(98). 제 1 그룹(66A)은 제 2 그룹(66B)의 비-제로 거리들(62)의 세트와 상이한 거리들(62)의 비-제로 세트를 포함한다. 즉, 거리들(62)은 제 1 및 제 2 그룹들(66)로 분할되어서, 거리들(62) 중 어느 하나도 양자의 그룹들(66)과 연관될 수 없다. 그룹핑 유닛(52)은 그룹들(66)을 매칭 유닛(54)에 출력한다. Upon receiving these
[0061] 그룹들(66)의 수신에 응답하여 매칭 유닛(54)은 제 1 그룹 거리들(66A)의 평균 및 제 2 그룹 거리들(66B)의 평균을 컴퓨팅한다(100). 이들 평균들은 그룹 평균(68A) 및 그룹 평균(68B)으로서 도 1의 예에서 도시되며, 여기서 그룹 평균(68A)은 그룹(66A)의 거리들(62)의 컴퓨팅된 평균을 표현하고 그룹 평균(68B)은 그룹(66B)의 거리들(62)의 컴퓨팅된 평균을 표현한다. 매칭 유닛(54)은 이어서 분할의 결과가 임계치(70) 미만인지를 결정하기 위해 분할의 결과를 임계치(70)에 비교하도록 그룹 평균(58B0로 그룹 평균(68A)을 나눈다(102-106). 결과가 임계치(70) 미만인 경우("예" 106), 매칭 유닛(54)은 질의 특징 기술자들(40) 중 선택된 것이 기준 특징 기술자들(51)의 결정된 가장 근처의 것에 매칭(거리(62)의 견지에서)한다고 식별하는 매칭 표시자(72)를 생성한다(108). 매칭 유닛(54)은 표시자(72) 및 제 1 그룹(66A)을 결과 생성기 유닛(56)에 포워딩한다. In response to receiving the groups 66, the matching unit 54 computes 100 the average of the first group distances 66A and the average of the second group distances 66B. These averages are shown in the example of FIG. 1 as group average 68A and group average 68B, where group average 68A represents the computed average of the
[0062] 결과 생성기 유닛(56)은 매칭 표시자(72) 및 그룹(66A)을 수신한다. 매칭 표시자(72) 및 그룹(66A)의 수신에 응답하여, 결과 생성기 유닛(56)은 리스트 형성 유닛(58)을 시동한다. 리스트 형성 유닛(58)은 위에서 기술된 방식으로 거리들(62)의 제 1 그룹(66A)과 연관된 기준 특징 기술자들(51)을 먼저 식별함으로써 초기 기준 영상 리스트(76)를 생성한다(110). 리스트 형성 유닛(58)은 다음으로, 재차 위에서 기술된 방식으로 기준 특징 기술자들(51)의 식별된 것들과 연관된 기준 영상들(53)을 식별한다(112). 리스트 형성 유닛(58)은 초기 기준 영상 리스트(76)로서 식별된 기준 영상들(53)을 저장할 수 있다. 또한, 위에서 기술된 바와 같이, 리스트 형성 유닛(58)은 이어서 식별된 기준 특징 기술자들(51)(또는 초기 기준 영상 리스트(76))에 기초하여 고유한 기준 영상들(53)의 리스트를 생성하며(114), 여기서 이 리스트는 고유한 기준 영상 리스트(74)로서 도 2의 예에서 도시된다. 결과 생성기 유닛(56)은 다음으로, 위에서 기술된 방식으로 고유한 기준 영상들(53)(또는 고유한 기준 영상 리스트(74))의 리스트에 보트들을 할당하는 보트 할당 유닛(60)을 시동할 수 있다(116). 보트 할당 유닛(60)은 고유한 기준 영상 리스트(74)에 의해 식별된 그러한 기준 영상들(53)에 보트들을 할당하도록 보트 집계 표(78)를 유지할 수 있다. [0062] The
[0063] 특징 매칭 유닛(36)은 이어서 그것이 위에서 기술된 방식으로 모든 질의 특징 기술자들(40)의 프로세싱을 완료하였는지를 결정한다(118). 대안적으로 매칭 유닛(54)은 그룹 평균(68B)으로 그룹 평균(68A)을 나눈 결과가 임계치(70) 미만이 아니라고 결정하는 경우(도 3a을 역으로 참조하여, "아니오"(106)), 특징 매칭 유닛(36)은 마찬가지로 그것이 위에서 기술된 방식으로 모든 질의 특징 기술자들(40)의 프로세싱을 완료하였다고 결정할 수 있다(118). 어떤 맥락에서, 특징 매칭 유닛(36)이 모든 질의 특징 기술자들(40의 프로세싱을 그것이 완료하였는지를 결정했는지 여부와 무관하게, 모든 질의 특징 기술자들(40)의 프로세싱을 완료하지 않은 경우,("아니오"(118)), 유닛들(50 내지 60)은 잔여 질의 특징 기술자들(40)을 프로세싱하도록 기술된 방식으로 동작한다(94 내지 118). The
[0064] 그러나, 모든 질의 특징 기술자들(40)의 프로세싱을 완료한 경우("예" (118)), 보트 할당 유닛(60)은 위에서 기술된 방식으로 할당된 보트들(보트 집계 표(78)에 의해 정의된 바와 같이)에 기초하여 기준 영상들(53)의 랭크된 리스트를 생성할 수 있다(120). 결과 생성기 유닛(56)은 이어서 기준 영상들(53)의 랭크된 리스트를 포함하도록 질의 결과 데이터(42)를 생성할 수 있다(122). 결과 생성기 유닛(56)은 이어서 클라이언트 디바이스(12)에 대한 인터페이스(32)를 통해 질의 결과 데이터(42)를 전송할 수 있다(124). However, when the processing of all
[0065] 도 4를 참조하면 특징 기술자 추출에서 이용하기 위해 결정된 DoG(difference of Gaussian) 피라미드(204)를 예시하는 다이어그램이다. 도 1의 특징 추출 유닛(18)은 가우시안 피라미드(202)에서 임의의 2개의 연속적인 가우시안-블러링된 영상들의 차이를 컴퓨팅함으로써 DoG 피라미드(204)를 구성할 수 있다. 도 1의 예에서 영상 데이터(26)로서 도시된 입력 영상(I(x, y))은 가우시안 피라미드(202)를 구성하도록 점진적으로 가우시안 블러링된다. 가우시안 블러링은 일반적으로 가우시안 블러링된 함수(L(x, y, cσ))가 L(x, y, cσ) = G(x, y, cσ)*I(x, y))로서 정의되도록 스케일 cσ에서 가우시안 블러 함수(G(x, y, cσ))로 원래의 영상(I(x, y))을 컨볼브하는 것을 포함한다. 여기서, G는 가우시안 커널이고, cσ는 영상(I(x, y))을 블러링하는데 이용되는 가우시안 함수의 표준 편차를 나타낸다. c가 변동되면(c0 < c1 < c2 < c3 < c4), 표준 편차(cσ)가 변동되고, 점진적인 블러링이 획득된다. 시그마 σ는 기본 스케일 변수(본질적으로 가우시안 커널의 폭)이다. 초기 영상(I(x, y))이 블러링된 영상들(L)을 생성하기 위해 가우시안(G)으로 증분적으로 컨볼브될 때, 블러링된 영상들(L)은 스케일 공간에서 상수 팩터(c)에 의해 분리된다. 4 is a diagram illustrating a difference of Gaussian (DoG)
[0066] DoG 공간 또는 피라미드(204)에서, D(x, y, a) = L(x, y, cnσ) - L(x, y, cn-1σ)이다. DoG 영상(D(x, y, σ))은 스케일들(cnσ및 cn-1σ)에서 2개의 가까운 가우시안 블러링된 영상들(L) 간의 차이이다. D(x, y, σ)의 스케일은 cnσ와 cn-1σ 사이 어딘가에 있다. 가우시안-블러링된 영상들(L)의 수가 증가하고 가우시안 피라미드(202)에 대해 제공된 근사가 연속적인 공간에 접근하면, 2개의 스케일들은 서로 하나의 스케일로 접근한다. 컨볼브된 영상들(L)은 옥타브(octave)에 의해 그룹핑될 수 있으며, 여기서 옥타브는 표준 편차 σ의 값의 2배에 대응한다. 또한, 승산기들의 값들(k)(예를 들어, c0 < c1 < c2 < c3 < c4)은 고정된 수의 컨볼브된 영상들(L)이 옥타브 당 획득되도록 선택된다. 이어서, DoG 영상들(D)은 옥타브 당 가까운 가우시안-블러링된 영상들(L)로부터 획득될 수 있다. 각각의 옥타브 이후에, 가우시안 영상은 2배로 다운-샘플링되고 이어서 프로세스가 반복된다. In the DoG space or
[0067] 특징 추출 유닛(18)은 이어서 영상(I(x, y))에 대한 키포인트들을 식별하기 위해 DoG 피라미드(204)를 이용할 수 있다. 키포인트 검출을 수행 시에, 특징 추출 유닛(18)은 영상 내의 특정한 샘플 지점 또는 픽셀 주위의 로컬 영역 또는 패치가 잠재적으로 흥미로운 패치(기하학적으로 말하면)인지를 결정한다. 일반적으로 특징 추출 유닛(18)은 DoG 공간(204)에서 로컬 최대 및/또는 로컬 최소를 식별하고 DoG 공간(204) 내의 키포인트 위치들로서 이들 최대 및 최소의 위치들을 이용한다. 도 4에 예시된 예에서, 특징 추출 유닛(18)은 패치(206) 내의 키포인트(208)를 식별한다. 로컬 최대 및 최소의 발견(또한 로컬 극단 검출로서 알려짐)은 총 26개의 픽셀들((9x2+8=26))에 대해, DoG 공간(204) 내의 각각의 픽셀(예를 들어, 키포인트(208)에 대한 픽셀)을 동일한 스케일에서의 그의 8개의 이웃하는 픽셀들에 그리고 2개의 측면들 상에서 이웃하는 스케일들 각각 내의 9개의 이웃하는 픽셀들(가까운 패치들(210 및 212)의)에 비교함으로써 달성될 수 있다. 키포인트(208)에 대한 픽셀 값이 패치들(206, 210 및 208)에서 모든 26개의 비교된 픽셀들 사이에서 최대 또는 최소인 경우, 특징 추출 유닛(18)은 이것을 키포인트로서 선택한다. 특징 추출 유닛(18)은 추가로 그의 위치가 보다 정확히 식별되도록 키포인트들을 추가로 프로세싱할 수 있다. 특징 추출 유닛(18)은 몇몇 인스턴스들에서, 저 콘트라스트 키 포인트들 및 에지 키 포인트들과 같은 키포인트들 중 일부를 폐기할 수 있다.
[0068] 도 5는 키포인트의 검출을 보다 상세히 예시하는 다이어그램이다. 도 5의 예에서, 패치들(206, 210 및 212) 각각은 3x3 픽셀 영역을 포함한다. 특징 추출 유닛(18)은 우선 흥미의 픽셀(예를 들어, 키포인트(208)를 동일한 스케일에서(예를 들어, 패치(206))의 그의 8개의 이웃하는 픽셀들(302)에, 그리고 키포인트(208)의 2개의 측면들 상의 이웃하는 스케일들 각각 내의 가까운 패치들(210 및 212) 내의 9개의 이웃하는 픽셀들(304 및 306)에 비교한다. 5 is a diagram illustrating in more detail the detection of a keypoint. In the example of FIG. 5, each of the
[0069] 특징 추출 유닛(18)은 로컬 영상 그라디언트의 방향들에 기초하여 하나 이상의 방위들, 또는 방향들을 각각의 키포인트에 할당할 수 있다. 로컬 영상 특성들에 기초하여 각각의 키포인트에 일관되는 방위를 할당함으로써, 특징 추출 유닛(18)은 이 방위에 대해 키포인트 식별자를 표현하고 이에 따라 영상 회전에 대한 불변성을 달성한다. 특징 추출 유닛(18)은 이어서 키포인트 스케일에서 및/또는 가우시안-블러링된 영상(L)의 키포인트(208) 주위의 이웃하는 영역들에서 각각의 픽셀에 대한 크기 및 방향을 계산한다. (x, y)에 위치되는 키포인트(208)에 대한 그라디언트의 크기는 m(x, y)로서 표현될 수 있고, (x, y)의 키포인트에 대한 그라디언트의 방위 또는 방향은 Γ(x, y)로서 표현될 수 있다. The
[0070] 특징 추출 유닛(18)은 이어서 모든 계산들이 스케일-불변 방식으로 수행되도록 키포인트(208)의 스케일에 대한 최근접 스케일을 갖는 가우시안 스무스드 영상(Gaussian smoothed image)(L)을 선택하도록 키포인트의 스케일을 이용한다. 이 스케일에서 각각의 영상 샘플 L(x, y)에 대해, 특징 추출 유닛(18)은 픽셀 차이들을 이용하여 그라디언트 크기, m(x, y) 및 방위 Γ(x, y)를 컴퓨팅한다. 예를 들어, 크기 m(x, y)는 다음의 수학식(2)에 따라 컴퓨팅될 수 있다:The
특징 추출 유닛(18)은 다음의 수학식(3)에 따라 방향 또는 방위(Γ(x, y))를 계산할 수 있다:The
수학식(3)에서, L(x, y)는 또한 키포인트의 스케일인 스케일 σ에서 가우시안-블러링된 영상(L(x, y, σ))의 샘플을 표현한다. In equation (3), L (x, y) also represents a sample of a Gaussian-blurred image L (x, y, σ) at scale σ, which is the scale of the keypoint.
[0071] 특징 추출 유닛(18)은 DoG 공간에서 키포인트의 평면 위에, 더 높은 스케일에 있는 가우시안 피라미드의 평면에 대해 또는 키포인트 아래, 더 낮은 스케일에 있는 가우시안 피라미드의 평면에서 키포인트에 대한 그라디언트를 일관되게 계산할 수 있다. 각각의 키포인트에 대해, 양자의 방식에서, 특징 추출 유닛(18)은 동일한 스케일에서 키포인트를 둘러싸는 직사각형 영역(예를 들어, 패치)에서 그라디언트를 계산한다. 또한, 영상 신호의 주파수는 가우시안-블러링 영상의 스케일에 반영된다. 아직, SIFT 및 CHoG(compressed histogram of gradients) 알고리즘과 같은 다른 알고리즘은 단순히 패치(예를 들어, 직사각형 지역) 내의 모든 픽셀들의 그라디언트 값들을 이용한다. 패치는 키포인트 주위로 정의되고; 서브-블록들은 블록 내에서 정의되고; 샘플들은 서브-블록들 내에 정의되고, 이러한 구조는 키포인트들의 스케일들이 상이할 때조차도 모든 키포인트들에 대해 동일하게 유지된다. 그러므로 영상 신호의 주파수가 동일한 옥타브에서 가우시안 스무싱 필터들(Gaussian smoothing filters)의 연속적인 적용을 통해 변경되지만, 상이한 스케일들에서 식별된 키포인트들은 스케일에 의해 표현되는 영상 신호의 주파수의 변화와 무관하게 동일한 수의 샘플들로 샘플링될 수 있다. The
[0072] 키포인트 방위를 특성화하기 위해, 특징 추출 유닛(18)은 예를 들어, SIFT를 이용함으로써 그라디언트 방위 히스토그램(도 6 참조)을 생성할 수 있다. 각각의 이웃한 픽셀들의 기여(contribution)는 그라디언트 크기 및 가우시안 윈도우에 의해 가중화될 수 있다. 히스토그램의 피크들을 지배적인 방위들에 대응한다. 특징 추출 유닛(18)은 키포인트 방위에 대한 키포인트의 모든 특성들을 측정할 수 있고, 이는 회전에 대한 불변성을 제공한다. To characterize the keypoint orientation,
[0073] 일 예에서, 특징 추출 유닛(18)은 각각의 블록에 대한 가우시안-가중화된 그라디언트의 분포를 컴퓨팅하며, 여기서 각각의 블록은 2개의 서브-블록 x 2개의 서브 블록이며 총 4개의 서브-블록들이 있다. 가우시안-가중화된 그라디언트들의 분포를 계산하기 위해, 특징 추출 유닛(18)은 몇 개의 빈(bin)들로 방위 히스토그램을 형성하며 각각의 빈은 키포인트 주위의 영역의 부분을 커버한다. 예를 들어, 방위 히스토그램은 36개의 빈들을 가질 수 있고, 각각의 빈은 360도 범위의 방위들 중 10도를 커버한다. 대안적으로, 히스토그램은 8개의 빈들을 가질 수 있고, 각각은 360도 범위 중 45도를 커버한다. 여기서 기술되는 히스토그램 코딩 기법들은 임의의 수의 빈들의 히스토그램들에 응용 가능할 수 있다는 것이 자명해져야 한다.In one example,
[0074] 도 6은 특징 추출 유닛(18)과 같은 특징 추출 유닛이 그라디언트 분포 및 방위 히스토그램을 결정하는 프로세스를 예시하는 다이어그램이다. 여기서, 2-차원 그라디언트 분포(dx, dy)(예를 들어, 블록(406))는 1-차원 분포(예를 들어, 히스토그램(414))로 변환된다. 키포인트(208)는 키포인트(208)를 둘러싸는 블록(406)의 중심(또한 패치, 셀 또는 영역으로 불림)에 위치된다. 피라미드의 각각의 레벨에 대해 사전-컴퓨팅되는 그라디언트들은 각각의 샘플 위치(48)에서 작은 화살표로서 도시된다. 도시된 바와 같이, 샘플들(408)의 영역들은 빈들(410)로서 또한 지칭될 수 있는 서브-블록들(410)을 형성한다. 특징 추출 유닛(18)은 서브-블록들 또는 빈들(410) 내의 각각의 샘플(408)에 가중치를 할당하기 위해 가우시안 가중화 함수를 이용할 수 있다. 가우시안 가중화 함수에 의한 샘플(408) 각각에 할당된 가중치는 빈들(410) 및 키포인트(208)의 중심으로부터 스무스하게 떨어진다. 가우시안 가중화 함수의 목적은 기술자의 중심으로부터 멀리 떨어진 그라디언트들에 더 적은 강조(emphasis)를 제공하고 윈도우의 위치에서 작은 변경들을 통해 기술자의 급작스런 변경들을 방기하기 위한 것이다. 특징 추출 유닛(18)은 차원 특징 기술자를 발생시키는 히스토그램의 각각의 빈의 8개의 방위들을 갖는 방위 히스토그램(412)의 어레이를 결정한다. 예를 들어, 방위 히스토그램(413)은 서브-블록(410)에 대한 그라디언트 분포에 대응할 수 있다. FIG. 6 is a diagram illustrating a process by which a feature extraction unit, such as
[0075] 몇몇 인스턴스들에서, 특징 추출 유닛(18)은 그라디언트 분포들을 획득하기 위해 다른 타입들의 양자화 빈 성상도들(quantization bin constellations)(예를 들어, 상이한 보로노이(Voronoi) 셀 구조들을 가짐)을 이용할 수 있다. 이러한 다른 타입들의 빈 성상도들은 마찬가지로 소프트 비닝(soft binning)의 형태를 이용할 수 있으며, 여기서 소프트 비닝은 이른바 DAISY 구성이 이용될 때 정의된 것들과 같은 오버랩하는 빈들을 지칭한다. 도 6의 예에서, 그러나 3개의 소프트 빈들이 정의되지만, 키포인트(208) 주위의 원형 구성(402)으로 일반적으로 위치되는 중심과 함께 9 또는 그 초과만큼 많이 이용될 수 있다. In some instances,
[0076] 여기서 이용되는 바와 같이, 히스토그램은 빈들로서 알려진 다양한 분리된 카테고리들 내에 있는 관찰들, 샘플 또는 발생(예를 들어, 그라디언트들)의 수를 카운트하는 맵(ki)이다. 히스토그램의 그래프는 히스토그램을 표현하기 위한 단지 하나의 방식이다. 따라서 k가 관찰들, 샘플들, 또는 발생들의 총 수이고 m인 빈들의 총 수인 경우, 히스토그램(ki)의 주파수는 수학식(4)으로서 표현되는 다음의 조건을 만족시킨다:As used herein, a histogram is a map k i that counts the number of observations, samples, or occurrences (eg, gradients) within various separate categories known as bins. Graphs of histograms are just one way to represent histograms. Thus, if k is the total number of observations, samples, or occurrences and the total number of bins, m, then the frequency of the histogram k i satisfies the following condition, expressed as equation (4):
여기서 는 합산 연산자이다. here Is an addition operator.
[0077] 특징 추출 유닛(18)은 키포인트의 스케일에 1.5배인 표준 편차를 갖는 가우시안-가중화된 함수에 의해 정의된 그의 그라디언트 크기에 의해 히스토그램들(412)에 부가된 각각의 샘플을 가중화한다. 결과적인 히스토그램(414)의 피크들은 로컬 그라디언트들의 지배적인 방향들에 대응한다. 특징 추출 유닛(18)은 이어서 히스토그램에서 최고 피크를 검출하고 이어서 최고 피크의 특정한 퍼센티지, 예를 들어, 80% 내에 있는 임의의 다른 로컬 피크를 검출한다(이것은 그 배향을 갖는 키포인트를 또한 생성하는데 또한 이용할 수 있음). 그러므로 유사한 크기의 다수의 피크들을 갖는 위치들에 대해, 특징 추출 유닛(18)은 위치 및 스케일이 동일하지만 상이한 방위로 생성되는 다수의 키포인트들을 추출한다.
[0078] 특징 추출 유닛(18)은 이어서 일 타입으로서 히스토그램을 표현하는 타입 양자화로서 지칭되는 양자화의 형태를 이용하여 히스토그램을 양자화한다. 이 방식으로, 특징 추출 유닛(18)은 각각의 키포인트에 대한 기술자를 추출할 수 있고, 여기서 각각의 기술자는 일 타입의 형태의 가우시안-가중화된 그라디언트들의 분포들의 위치(x, y) 및 방위 및 기술자에 의해 특성화될 수 있다. 이러한 방식으로, 영상은 하나 이상의 키포인트 기술자들(또한 영상 기술자들로서 지칭됨)에 의해 특성화될 수 있다.
[0079] 도 4 내지 도 6에서 도시된 위의 예들이 SIFT 알고리즘에 의해 수행되는 특징 추출의 일 예를 제공하지만, 기법들은 CHoG(compressed histogram of gradient) 알고리즘과 같은 임의의 다른 비주얼 탐색 알고리즘에 따라 추출되는 특징 기술자들에 관해 구현될 수 있다. 그러므로 기법들은 이러한 점에서 SIFT 알고리즘을 이용하여 추출된 특징 기술자들만으로 제한되어야 하는 것이 아니라, 임의의 비주얼 탐색 알고리즘에 따라 추출된 특징 기술자들에 관하여 구현될 수 있다. While the above examples shown in FIGS. 4-6 provide an example of feature extraction performed by a SIFT algorithm, the techniques are in accordance with any other visual search algorithm, such as a compressed histogram of gradient (CHoG) algorithm. It may be implemented with respect to the feature descriptors being extracted. Therefore, the techniques should not be limited to feature descriptors extracted using SIFT algorithm in this respect, but may be implemented with respect to feature descriptors extracted according to any visual search algorithm.
[0080] 도 7은 본 개시에서 기술되는 기법들에 따라 특징 매칭을 수행하는데 있어 도 1의 특징 매칭 유닛(36)과 같은 특징 매칭 유닛의 예시적인 동작을 예시하는 다이어그램이다. 도 7의 예에서, 질의 영상 데이터(500) 및 기준 영상 데이터(502)가 도시되며, 여기서 질의 영상 데이터(500)는 기준 영상 데이터(502)의 좌측에 도시된다. 흑색 라인들은 특징 기술자 데이터베이스(38)에 저장되고 기준 영상 데이터(502)로부터 추출된 (우측 화살표 머리에 의해 표현되는) 기준 특징 기술자들과 질의 영상 데이터로부터 추출된 (이용 가능한 경우 좌측 화살표 머리에 의해 표현되는) 질의 특징 기술자들 간의 관계를 도시한다. FIG. 7 is a diagram illustrating an example operation of a feature matching unit, such as
[0081] 질의 영상 데이터(500)는 클라이언트 디바이스(12)와 같은 클라이언트 디바이스에 의해 캡처되거나 또는 다른 방식으로 획득된 피사의 사탑의 영상을 도시한다. 질의 영상 데이터(500) 및 기준 영상 데이터(502)는 상이한 (비록 유사하지만) 관점에서 그리고 상이한 스케일들로서 캡처되는 피사의 사탑의 영상들을 도시한다. 비주얼 탐색 서버(14)의 특징 매칭 유닛(36)은 이 예에서 좌측 화살표들로 표시되는 특징들을 표현하는 질의 특징 기술자들(40)을 수신한다. 특징 매칭 유닛(36)은 우측 화살표에 의해 표시되는 대응하는 특징들을 표현하는 매칭 기준 특징 기술자들(51)(도 2를 참조)을 결정한다.
[0082] 이 예에서, 피사의 사탑은 피사의 사탑을 둘러싸는 반복 아치들의 형태의 다수의 반복 구조들을 포함한다. 특히 504A 내지 504C로 표시되는 3개의 흑색 라인들은 특징 기술자 공간에서 서로 근접할 수 있는 기준 특징 기술자들과 대응하는 질의 간의 잠재적인 매칭을 예시한다. 종래의 비주얼 탐색 알고리즘에서 공통적이었던 바와 같이 고유하지 않은 것으로서 이들 매칭들을 거절하기 보단 오히려, 특징 매칭 유닛(36)은 이들 라인들(504A 내지 504C)의 좌측 화살표들에 의해 표현되는 대응하는 질의 특징 기술자들(40)의 각각에 대하여, 서로에 관해 제 1 그룹(66A)에서 그룹핑되는 거리(62)(재차 도 2 참조)를 결정할 수 있다. In this example, the leaning tower of Pisa includes a number of repeating structures in the form of repeating arches surrounding the leaning tower of Pisa. In particular, the three black lines, labeled 504A-504C, illustrate a potential match between a reference feature descriptor and a corresponding query that may be close to each other in the feature descriptor space. Rather than rejecting these matches as not unique as was common in conventional visual search algorithms,
[0083] 예를 들어, 라인(504A)에 의해 표시되는 매칭을 고려하면, 특징 매칭 유닛(36)은 라인(504A)의 좌측 화살표에 의해 표현되는 질의 특징 기술자들(40)이 라인들(504A 내지 504C는 물론 504D 내지 504G) 각각에 대한 우측 화살표들에 의해 표현되는 기준 특징 기술자들(51)에 매칭한다고 결정할 수 있다. 특징 매칭 유닛(36)은 위에서 기술된 방식으로 라인들(504A 내지 504G)과 연관되는 기준 특징 기술자들(51)에 대해 라인(504A)과 연관된 질의 특징 기술자(40)에 관한 거리들(62)을 결정할 수 있다. 다음으로, 특징 매칭 유닛(36)은 라인(504A)과 연관된 질의 특징 기술자 및 라인들(504A 내지 504C)과 연관된 기준 특징 기술자들에 관해 컴퓨팅된 거리들(62)을 그룹핑할 수 있고 다른 그룹은 모든 잔여 거리들을 포함한다. 특징 매칭 유닛(36)은 이어서 제 1 및 제 2 그룹 거리들(66)을 평균화하고 제 2 그룹 평균(68B)으로 제 1 그룹 평균(68A)을 나누고 나눈 결과를 임계치(70)에 비교할 수 있다. 특징 매칭 유닛(36)은 이 예에서 고유한 매칭을 결정하고 그에 의해 라인(504A)으로서 도시된 매칭을 결정한다. For example, considering the match indicated by
[0084] SIFT와 같은 비주얼 탐색 알고리즘들의 종래의 특징 매칭 양상들은 클러스터링 알고리즘을 이용하지 않음으로써 라인(504A)에 의해 표현되는 매칭을 거절할 수 있다. 이러한 매칭의 거절은 라인(504A)의 좌측 화살표에 의해 표현되는 특징으로부터 추출된 질의 특징 기술자(40) 및 라인(504A)의 우측 화살표에 의해 표현되는 특징으로부터 추출되는 기준 특징 기술자(51)가 최소일 것이기 때문에 발생할 수 있다. 이 예에서, 다음의 최소 거리는 라인(504A)의 좌측 화살표에 의해 표현되는 특징으로부터 추출된 질의 특징 기술자(40)와 라인(504B)의 우측 화살표에 의해 표현되는 특징으로부터 추출되는 기준 특징 기술자(51) 간의 거리일 것이다. 이 다음의 최소 거리는 거의 위에서 언급된 최소 거리 만큼 작을 수 있다. 따라서 비주얼 탐색 알고리즘들의 종래의 특징 매칭 양상들에 따라 다음의 최소 거리로 최소 거리를 나누면 임계치보다 클 수 있는 1에 가까운 번호가 발생할 수 있으며, 이는 통상적으로 0.5와 같이 1의 임의의 단편으로 세팅된다. Conventional feature matching aspects of visual search algorithms, such as SIFT, may reject the match represented by
[0085] 따라서 본 개시에서 기술되는 기법들에 따라 그룹들을 결정하기 위해 클러스터링 알고리즘을 이용함으로써, 특징 매칭 유닛(36)은 반복 특징 패턴들을 참조하는 이들 비교적 작은 거리들(62) 모두를 제 1 그룹(66A)으로 그룹핑할 수 있는 반면에, 모든 다른 거리들(62)은 제 2 그룹(그룹 66B)으로 그룹핑될 수 있다. 특징 매칭 유닛(36)은 이어서 이들 그룹들 각각의 비교를 용이하게 하도록 이들 거리들을 평균화하고 가능하게는 고유한 매칭으로 간주되는 것을 거절하는 것을 방지하도록 이 평균들을 비교한다. 그 결과, 기법들은 특히, 반복 특징들 또는 양상들을 갖는 영상들에 관하여 특징 매칭을 개선할 수 있다. Thus, by using a clustering algorithm to determine groups in accordance with the techniques described in this disclosure,
[0086] 또한, 틀린 매칭의 수락에 관한 제어를 유지하면서 잠재적인 매칭들의 거절을 방지하기 위해, 본 개시의 강건한 거리 비 기법들은 위에서 기술된 보다 차별적인 유사사어 측정을 제공한다. 강건한 거리 비 기법들은 k-차원 트리(KD-트리)-베스트 빈 퍼스트(Best Bin First)를 이용하여 최초의 가장 근처의 이웃에 대해 질의하면서 저장된 중간 데이터를 이용함으로써 약간의 내지 전혀 없는 오버헤드 컴퓨팅 비용으로 수행될 수 있다. In addition, the robust distance ratio techniques of the present disclosure provide the more discriminatory quasi-measurement measures described above, in order to prevent rejection of potential matches while maintaining control over acceptance of the wrong match. Robust distance-ratio techniques use little to no overhead computing by using stored intermediate data while querying the first nearest neighbor using the k-dimensional tree-Best Bin First. It can be done at a cost.
[0087] 하나 이상의 예들에서, 기술된 기능들은 하드웨어, 소프트웨어, 펌웨어, 또는 이들의 임의의 조합으로 구현될 수 있다. 소프트웨어로 구현되는 경우, 기능들은 컴퓨터-판독 가능한 매체 상의 하나 이상의 명령들 또는 코드로서 저장되거나, 또는 이를 통해 전송될 수 있다. 컴퓨터-판독 가능한 매체들은 컴퓨터 데이터 저장 매체들을 포함할 수 있다. 데이터 저장 매체들은 본 개시에서 기술된 기법들의 구현을 위해 명령들, 코드 및/또는 데이터 구조들을 리트리브하도록 하나 이상의 컴퓨터들 또는 하나 이상의 프로세서들에 의해 액세스될 수 있는 임의의 이용 가능한 매체들일 수 있다. 여기서 이용되는 바와 같은 "데이터 저장 매체"는 제조품을 지칭하며 일시적인 전파 신호들을 지칭하지 않는다. 제한이 아닌 예로서, 이러한 컴퓨터-판독 가능한 매체들은 RAM, ROM, EEPROM, CD-ROM 또는 다른 광학 디스크 저장소, 자기 디스크 저장 또는 다른 자기 저장 디바이스들, 플래시 메모리, 또는 컴퓨터에 의해 액세스될 수 있고 데이터 구조 또는 명령들의 형태로 원하는 프로그램 코드를 저장하는데 이용될 수 있는 임의의 다른 매체를 포함할 수 있다. 본 명세서에서 사용되는 디스크(disk) 및 디스크(disc)는 컴팩트 디스크(disc)(CD), 레이저 디스크(disc), 광 디스크(disc), 디지털 다기능 디스크(disc)(DVD), 플로피 디스크(disk), 및 블루-레이 디스크(disc)를 포함하며, 여기서 디스크(disk)들은 데이터를 보통 자기적으로 재생하지만, 디스크(disc)들은 레이저를 이용하여 광학적으로 데이터를 재생한다. 상기한 것들의 조합들 역시 컴퓨터 판독가능 매체들의 범위 내에 포함되어야 한다.In one or more examples, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media may include computer data storage media. Data storage media may be any available media that can be accessed by one or more computers or one or more processors to retrieve instructions, code and / or data structures for implementation of the techniques described in this disclosure. "Data storage medium" as used herein refers to an article of manufacture and does not refer to transient propagation signals. By way of example, and not limitation, such computer-readable media may be RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, flash memory, or computer accessible data. It can include any other medium that can be used to store the desired program code in the form of structures or instructions. As used herein, a disc and a disc may be a compact disc (CD), a laser disc, an optical disc, a digital versatile disc (DVD), a floppy disc ), And Blu-ray discs, where discs usually reproduce data magnetically, while discs reproduce data optically using a laser. Combinations of the above should also be included within the scope of computer readable media.
[0088] 코드는 하나 이상의 DSP들(digital signal processors), 범용 마이크로프로세서들, ASIC들(application specific integrated circuits), FPGA(field programmable logic arrays)들, 또는 다른 등가의 통합된 또는 이상 로직 회로와 같은 하나 이상의 프로세서들에 의해 실행될 수 있다. 이에 따라, 여기서 이용된 바와 같은 용어 "프로세서"는 위의 구조 또는 여기서 기술된 기법들의 구현에 적합한 임의의 다른 구조 중 임의의 것을 지칭할 수 있다. 또한, 몇몇 양상들에서, 여기서 기술된 기능은 코딩 및 디코딩을 위해 구성되는 전용 하드웨어 및/또는 소프트웨어 모듈들 내에 제공될 수 있거나 조합된 코덱에 통합될 수 있다. 또한, 기법들은 하나 이상의 회로들 또는 로직 엘리먼트들에서 완전히 구현될 수 있다. The code may be one or more digital signal processors (DSPs), general purpose microprocessors, application specific integrated circuits (ASICs), field programmable logic arrays (FPGAs), or other equivalent integrated or abnormal logic circuits. It may be executed by one or more processors. As such, the term “processor” as used herein may refer to any of the above structures or any other structure suitable for the implementation of the techniques described herein. In addition, in some aspects, the functionality described herein may be provided within dedicated hardware and / or software modules configured for coding and decoding or integrated into a combined codec. Techniques may also be fully implemented in one or more circuits or logic elements.
[0089] 본 개시의 기법들은 무선 핸드셋, 집적 회로(IC) 또는 IC들의 세트(예를 들어, 칩 세트)를 포함하는 매우 다양한 디바이스들 또는 장치들로 구현될 수 있다. 다양한 컴포넌트들, 모듈들, 또는 유닛들은 기재된 기법들을 수행하도록 구성된 디바이스들의 기능적인 양상들을 강조하기 위해 본 개시에서 기술되었지만, 반드시 상이한 하드웨어 유닛들에 의한 실현을 요구하는 것은 아니다. 오히려, 위에서 기술된 바와 같이, 다양한 유닛들은 컴퓨터-판독 가능한 매체 상에 저장된 적합한 소프트웨어 및/또는 펌웨어와 함께 위에서 기술된 바와 같은 하나 이상의 프로세서들을 포함하는 상호작용식 하드웨어 유닛들의 모음에 의해 또는 코덱 하드웨어 유닛으로 조합될 수 있다. The techniques of this disclosure may be implemented in a wide variety of devices or apparatuses, including a wireless handset, an integrated circuit (IC), or a set of ICs (eg, a chip set). Various components, modules, or units have been described in this disclosure to emphasize functional aspects of devices configured to perform the described techniques, but do not necessarily require realization by different hardware units. Rather, as described above, the various units may be coded hardware or by a collection of interactive hardware units including one or more processors as described above in conjunction with suitable software and / or firmware stored on a computer-readable medium. Can be combined into units.
다응? 예들이 기술되었다. 이들 및 다른 예들은 다음의 청구항들의 범위 내에 있다.
Are you? Examples have been described. These and other examples are within the scope of the following claims.
Claims (41)
상기 비주얼 탐색 디바이스를 통해, 비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하는 단계 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ;
상기 비주얼 탐색 디바이스를 통해, 클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하는 단계 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및
상기 비주얼 탐색 디바이스를 통해, 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계
를 포함하는,
비주얼 탐색을 수행하기 위한 방법.A method for performing visual navigation via a visual navigation device, the method comprising:
Computing, via the visual search device, a distance between a query feature descriptor provided by a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search;
Determining, via the visual navigation device, one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is determined by the plurality of criteria. The second group of computed distances includes those of computed distances indicating that an association of feature descriptors is near to the query feature descriptor relative to those of the computed distances determined to be within the second group of computed distances. The computed distances indicating that the association of the plurality of reference feature descriptors is away from the query feature descriptor relative to those of the computed distances determined to be within one or more first groups of the computed distances; And
Via the visual search device, a plurality of reference feature descriptors with which the query feature descriptor is associated with the least of the computed distances based on the determined first group of computed distances and the second group of computed distances. Determining whether to match one of the
/ RTI >
Method for performing visual navigation.
상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹을 결정하는 단계는,
k-평균 클러스터링 알고리즘(k-means clustering algorithm), 가우시안 피팅 알고리즘(Gaussian fitting algorithm) 및 그래픽 컷팅 알고리즘(graph cutting algorithm) 중 하나 이상에 따라 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹을 결정하는 단계를 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 1,
Determining the one or more first group of computed distances and the second group of computed distances,
one or more first groups of computed distances and the computed distances according to one or more of a k-means clustering algorithm, a Gaussian fitting algorithm, and a graph cutting algorithm Determining a second group of subjects,
Method for performing visual navigation.
상기 질의 특징 기술자가 상기 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계는,
제 1 그룹 거리 평균을 생성하기 위해 상기 제 1 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 2개 이상의 평균을 컴퓨팅하는 단계;
제 2 그룹 거리 평균을 생성하기 위해 상기 제 2 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 평균을 컴퓨팅하는 단계;
평균 거리 비 측정(average distance ratio measure)을 생성하기 위해 상기 제 2 그룹 거리 평균으로 상기 제 1 그룹 거리 평균을 나누는 단계;
상기 평균 거리 비 측정을 임계값에 비교하는 단계; 및
상기 비교에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들의 최소의 것에 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계
를 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 1,
Determining if the query feature descriptor matches one of the plurality of reference feature descriptors,
Computing at least two averages of the computed distances determined to be within the first group to produce a first group distance average;
Computing an average of the computed distances determined to be within the second group to produce a second group distance average;
Dividing the first group distance average by the second group distance average to produce an average distance ratio measure;
Comparing the average distance ratio measurement to a threshold; And
Based on the comparison, determining whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the minimum of the computed distances.
/ RTI >
Method for performing visual navigation.
기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하는 단계;
상기 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트(vote)를 할당하는 단계;
할당된 보트에 기초하여 상기 기준 영상들을 순서화하는 단계; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴(return)하는 단계
를 더 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 1,
A reference such that the computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images include reference images associated with those of the plurality of reference feature descriptors computed for the corresponding group of reference feature descriptors. Determining a unique group of images;
Assigning a bot to each of the reference images determined to be in a unique group of the reference images;
Ordering the reference images based on the assigned boat; And
Returning ordered reference images in response to the visual search query
≪ / RTI >
Method for performing visual navigation.
상기 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당하는 단계는,
상기 기준 영상들 각각에 상수 보트를 할당하는 단계;
상기 질의 특징 기술자와 상기 복수의 기준 특징 기술자들 중 최근접의 것 간의 컴퓨팅된 거리에 비견되는 대응하는 컴퓨팅된 거리의 거리 비에 비례하여 보트를 할당하는 단계; 및
상기 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대로 순서화될 때 상기 제 1 그룹 내의 대응하는 컴퓨팅된 거리의 랭크(rank)에 비례하여 보트를 할당하는 단계
중 하나 이상을 포함하는,
비주얼 탐색을 수행하기 위한 방법.5. The method of claim 4,
Assigning a boat to each of the reference images determined to be in a unique group of the reference images,
Assigning a constant boat to each of the reference images;
Assigning a boat in proportion to a distance ratio of a corresponding computed distance that is comparable to the computed distance between the query feature descriptor and the nearest one of the plurality of reference feature descriptors; And
Allocating a boat in proportion to the rank of the corresponding computed distance in the first group when the computed distances of the first group are ordered from minimum to maximum
≪ / RTI >
Method for performing visual navigation.
상기 질의 특징 기술자는 상기 비주얼 탐색 질의에 의해 제공되고 비주얼 탐색 알고리즘에 따라 질의 영상 데이터로부터 추출된 복수의 질의 특징 기술자들 중 하나를 포함하고,
상기 방법은,
상기 복수의 질의 특징 기술자들 각각에 대해, 컴퓨팅된 복수의 거리들을 생성하기 위해 상기 복수의 질의 특징 기술자들 중 현재의 것과 상기 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하는 단계;
상기 복수의 거리들 각각에 대해, 상기 클러스터링 알고리즘에 따라 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹을 결정하는 단계 - 상기 컴퓨팅된 복수의 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 그룹들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고, 상기 컴퓨팅된 복수의 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 복수의 질의 특징 기술자들 중 현재의 것으로부터 떨어져 있다고 표시하는 컴퓨팅된 복수의 거리들의 것들을 포함함 - ; 및
상기 비주얼 탐색 디바이스를 통해, 상기 복수의 질의 특징 기술자들 각각이 상기 컴퓨팅된 복수의 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹에 기초하여 상기 컴퓨팅된 복수의 거리들의 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계
를 더 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 1,
The query feature descriptor includes one of a plurality of query feature descriptors provided by the visual search query and extracted from query image data according to a visual search algorithm,
The method comprises:
For each of the plurality of query feature descriptors, computing a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to produce a plurality of computed distances;
For each of the plurality of distances, determining a first group of the computed plurality of distances and a second group of the computed plurality of distances according to the clustering algorithm-a first group of the computed plurality of distances Includes those of computed distances indicating that the associated of the plurality of reference feature descriptors is near to the query feature descriptor relative to those of the computed plurality of distances determined to be within the second group of the computed plurality of groups. And wherein the second group of computed plurality of distances is associated with the plurality of query features relative to those of the computed plurality of distances that are associated with the plurality of reference feature descriptors within a first group of the computed plurality of distances. The com which marks the engineer as being separated from the current one Tingdoen including ones of the plurality of distances; And
With the visual search device, each of the plurality of query feature descriptors is configured to determine a minimum of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances. Determining one of a plurality of reference feature descriptors associated with the
≪ / RTI >
Method for performing visual navigation.
상기 복수의 질의 특징 기술자들 각각에 대해, 기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하는 단계;
상기 복수의 질의 특징 기술자들 각각에 대해 결정된 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당하는 단계;
상기 복수의 질의 특징 기술자들 각각에 대해 보트들을 할당한 이후, 할당된 보트들에 기초하여 상기 기준 영상들을 순서화하는 단계; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴하는 단계
를 더 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method according to claim 6,
For each of the plurality of query feature descriptors, the plurality of computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images are computed for the corresponding group of reference feature descriptors. Determining a unique group of reference images to include reference images associated with those of the reference feature descriptors;
Assigning a boat to each of the reference images determined to be in a unique group of reference images determined for each of the plurality of query feature descriptors;
After allocating boats for each of the plurality of query feature descriptors, ordering the reference images based on the assigned boats; And
Returning ordered reference images in response to the visual search query
≪ / RTI >
Method for performing visual navigation.
상기 질의 특징 기술자는,
로컬 특징-기반 비주얼 탐색 알고리즘에 따라 질의 영상으로부터 추출되는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 1,
The feature descriptor of the above quality,
Extracted from the query image according to a local feature-based visual search algorithm,
Method for performing visual navigation.
상기 로컬-특징 기반 비주얼 탐색 알고리즘은,
SIFT(scale invariant feature transform) 알고리즘을 포함하는,
비주얼 탐색을 수행하기 위한 방법.The method of claim 8,
The local-feature based visual search algorithm,
Including a scale invariant feature transform (SIFT) algorithm,
Method for performing visual navigation.
클라이언트 디바이스로부터 비주얼 탐색 디바이스의 인터페이스를 통해 압축된 질의 특징 기술자로서 상기 질의 특징 기술자를 수신하는 단계; 및
상기 비주얼 탐색 디바이스를 통해 상기 압축된 질의 특징 기술자로부터 상기 질의 특징 기술자를 재구성하는 단계
를 더 포함하는,
비주얼 탐색을 수행하기 위한 방법. The method of claim 1,
Receiving the query feature descriptor as a compressed query feature descriptor from a client device through an interface of a visual navigation device; And
Reconstructing the query feature descriptor from the compressed query feature descriptor via the visual search device.
≪ / RTI >
Method for performing visual navigation.
비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하기 위한 수단 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ;
클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하기 위한 수단 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및
상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하는 단계
를 포함하는,
비주얼 탐색을 수행하기 위한 장치.An apparatus for performing visual navigation,
Means for computing a distance between each of a plurality of reference feature descriptors and a query feature descriptor provided by a visual search query, wherein the visual search query initiates the visual search;
Means for determining one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is associated with the plurality of reference feature descriptors. And those of computed distances indicating that the query feature descriptor is near relative to those of the computed distances determined to be within the second group of computed distances, wherein the second group of computed distances is the plurality of reference feature descriptors. Includes those of computed distances indicating that the association of the distance from the query feature descriptor is relative to those of the computed distances determined to be within the one or more first groups of computed distances; And
Determining whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the least of the computed distances based on the determined first group of computed distances and the second group of computed distances. step
/ RTI >
Device for performing visual navigation.
k-평균 클러스터링 알고리즘(k-means clustering algorithm), 가우시안 피팅 알고리즘(Gaussian fitting algorithm) 및 그래픽 컷팅 알고리즘(graph cutting algorithm) 중 하나 이상에 따라 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹을 결정하기 위한 수단
을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 11,
one or more first groups of computed distances and the computed distances according to one or more of a k-means clustering algorithm, a Gaussian fitting algorithm, and a graph cutting algorithm Means for determining a second group of people
≪ / RTI >
Device for performing visual navigation.
제 1 그룹 거리 평균을 생성하기 위해 상기 제 1 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 2개 이상의 평균을 컴퓨팅하기 위한 수단;
제 2 그룹 거리 평균을 생성하기 위해 상기 제 2 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 평균을 컴퓨팅하기 위한 수단;
평균 거리 비 측정을 생성하기 위해 상기 제 2 그룹 거리 평균으로 상기 제 1 그룹 거리 평균을 나누기 위한 수단;
상기 평균 거리 비 측정을 임계값에 비교하기 위한 수단; 및
상기 비교에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들의 최소의 것에 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하기 위한 수단
을 포함하는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 11,
Means for computing two or more averages of the computed distances determined to be within the first group to produce a first group distance average;
Means for computing an average of the computed distances determined to be within the second group to produce a second group distance average;
Means for dividing the first group distance average by the second group distance average to produce an average distance ratio measurement;
Means for comparing the average distance ratio measurement to a threshold; And
Means for determining whether the query feature descriptor matches one of a plurality of reference feature descriptors associated with the minimum of the computed distances based on the comparison
Including,
Device for performing visual navigation.
기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하기 위한 수단;
상기 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트(vote)를 할당하기 위한 수단;
할당된 보트에 기초하여 상기 기준 영상들을 순서화하기 위한 수단; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴(return)하기 위한 수단
을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 11,
A reference such that the computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images include reference images associated with those of the plurality of reference feature descriptors computed for the corresponding group of reference feature descriptors. Means for determining a unique group of images;
Means for assigning a bot to each of the reference images determined to be in a unique group of the reference images;
Means for ordering the reference images based on the assigned boat; And
Means for returning ordered reference images in response to the visual search query
≪ / RTI >
Device for performing visual navigation.
상기 기준 영상들 각각에 상수 보트를 할당하기 위한 수단;
상기 질의 특징 기술자와 상기 복수의 기준 특징 기술자들 중 최근접의 것 간의 컴퓨팅된 거리에 비견되는 대응하는 컴퓨팅된 거리의 거리 비에 비례하여 보트를 할당하기 위한 수단; 및
상기 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대로 순서화될 때 상기 제 1 그룹 내의 대응하는 컴퓨팅된 거리의 랭크(rank)에 비례하여 보트를 할당하기 위한 수단
중 하나 이상을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치.15. The method of claim 14,
Means for assigning a constant boat to each of the reference images;
Means for assigning a boat in proportion to a distance ratio of a corresponding computed distance that is comparable to a computed distance between the query feature descriptor and the nearest one of the plurality of reference feature descriptors; And
Means for allocating a boat in proportion to the rank of the corresponding computed distance in the first group when the computed distances of the first group are ordered from minimum to maximum
More than one,
Device for performing visual navigation.
상기 질의 특징 기술자는 상기 비주얼 탐색 질의에 의해 제공되고 비주얼 탐색 알고리즘에 따라 질의 영상 데이터로부터 추출된 복수의 질의 특징 기술자들 중 하나를 포함하고,
상기 장치는,
상기 복수의 거리들 각각에 대해, 컴퓨팅된 복수의 거리들을 생성하기 위해 상기 복수의 질의 특징 기술자들 중 현재의 것과 상기 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하기 위한 수단;
상기 복수의 거리들 각각에 대해, 상기 클러스터링 알고리즘에 따라 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹을 결정하기 위한 수단 - 상기 컴퓨팅된 복수의 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 그룹들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고, 상기 컴퓨팅된 복수의 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 복수의 질의 특징 기술자들 중 현재의 것으로부터 떨어져 있다고 표시하는 컴퓨팅된 복수의 거리들의 것들을 포함함 - ; 및
상기 복수의 질의 특징 기술자들 각각이 상기 컴퓨팅된 복수의 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹에 기초하여 상기 컴퓨팅된 복수의 거리들의 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하기 위한 수단
을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 11,
The query feature descriptor includes one of a plurality of query feature descriptors provided by the visual search query and extracted from query image data according to a visual search algorithm,
The apparatus comprises:
Means for computing, for each of the plurality of distances, a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to produce a plurality of computed distances;
Means for determining, for each of the plurality of distances, a first group of the computed plurality of distances and a second group of the computed plurality of distances according to the clustering algorithm-a first of the computed plurality of distances The group includes those of computed distances indicating that the associated of the plurality of reference feature descriptors is near to the query feature descriptor as compared to those of the computed plurality of distances determined to be within the second group of the computed plurality of groups. And wherein the second group of computed plurality of distances comprises the plurality of queries relative to those of the computed plurality of distances that are associated with the plurality of reference feature descriptors to be within the first group of computed plurality of distances. Mark the feature descriptors apart from the current one. Including ones of a plurality of computing the distance; And
Each of the plurality of query feature descriptors associated with a minimum of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances. Means for determining whether to match one of the
≪ / RTI >
Device for performing visual navigation.
상기 복수의 질의 특징 기술자들 각각에 대해, 기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하기 위한 수단;
상기 복수의 질의 특징 기술자들 각각에 대해 결정된 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당하기 위한 수단;
상기 복수의 질의 특징 기술자들 각각에 대해 보트들을 할당한 이후, 할당된 보트들에 기초하여 상기 기준 영상들을 순서화하기 위한 수단; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴하기 위한 수단
을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치.17. The method of claim 16,
For each of the plurality of query feature descriptors, the plurality of computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images are computed for the corresponding group of reference feature descriptors. Means for determining a unique group of reference images to include reference images associated with those of the reference feature descriptors;
Means for assigning a boat to each of the reference images determined to be in a unique group of reference images determined for each of the plurality of query feature descriptors;
Means for ordering the reference images based on assigned boats after allocating boats for each of the plurality of query feature descriptors; And
Means for returning ordered reference images in response to the visual search query
≪ / RTI >
Device for performing visual navigation.
상기 질의 특징 기술자는,
로컬 특징-기반 비주얼 탐색 알고리즘에 따라 질의 영상으로부터 추출되는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 11,
The feature descriptor of the above quality,
Extracted from the query image according to a local feature-based visual search algorithm,
Device for performing visual navigation.
상기 로컬-특징 기반 비주얼 탐색 알고리즘은,
SIFT(scale invariant feature transform) 알고리즘을 포함하는,
비주얼 탐색을 수행하기 위한 장치.The method of claim 18,
The local-feature based visual search algorithm,
Including a scale invariant feature transform (SIFT) algorithm,
Device for performing visual navigation.
클라이언트 디바이스로부터 비주얼 탐색 디바이스의 인터페이스를 통해 압축된 질의 특징 기술자로서 상기 질의 특징 기술자를 수신하기 위한 수단; 및
상기 비주얼 탐색 디바이스를 통해 상기 압축된 질의 특징 기술자로부터 상기 질의 특징 기술자를 재구성하기 위한 수단
을 더 포함하는,
비주얼 탐색을 수행하기 위한 장치. The method of claim 11,
Means for receiving the query feature descriptor as a compressed query feature descriptor from a client device through an interface of a visual navigation device; And
Means for reconstructing the query feature descriptor from the compressed query feature descriptor via the visual search device.
≪ / RTI >
Device for performing visual navigation.
질의 특징 기술자를 수신하도록 구성된 인터페이스;
특징 매칭 유닛을 포함하고,
상기 특징 매칭 유닛은,
비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하도록 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ; 및
클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하도록
구성되고
상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및
상기 특징 매칭 유닛은 상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하도록 추가로 구성되는,
비주얼 탐색을 수행하기 위한 장치.A device configured to perform visual navigation,
An interface configured to receive a query feature descriptor;
A feature matching unit,
The feature matching unit,
To compute a distance between a query feature descriptor provided by a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search; And
Determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm.
Configured
The first group of computed distances is computed to indicate that an associated of the plurality of reference feature descriptors is near to the query feature descriptor as compared to those of the computed distances determined to be within the second group of computed distances. A second group of computed distances, including those of distances, that the associated of the plurality of reference feature descriptors is away from the query feature descriptor relative to those of the computed distances determined to be within the one or more first groups of computed distances. Include those of the computed distances to indicate; And
The feature matching unit is one of a plurality of reference feature descriptors with which the query feature descriptor is associated with the least of the computed distances based on the determined first group of computed distances and the second group of computed distances. Further configured to determine whether to match
Device for performing visual navigation.
상기 특징 매칭 유닛은,
k-평균 클러스터링 알고리즘(k-means clustering algorithm), 가우시안 피팅 알고리즘(Gaussian fitting algorithm) 및 그래픽 컷팅 알고리즘(graph cutting algorithm) 중 하나 이상에 따라 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹을 결정하도록
구성되는,
비주얼 탐색을 수행하기 위한 장치.22. The method of claim 21,
The feature matching unit,
one or more first groups of computed distances and the computed distances according to one or more of a k-means clustering algorithm, a Gaussian fitting algorithm, and a graph cutting algorithm To determine the second group of
Configured,
Device for performing visual navigation.
상기 특징 매칭 유닛은 추가로,
제 1 그룹 거리 평균을 생성하기 위해 상기 제 1 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 2개 이상의 평균을 컴퓨팅하도록;
제 2 그룹 거리 평균을 생성하기 위해 상기 제 2 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 평균을 컴퓨팅하도록;
평균 거리 비 측정을 생성하기 위해 상기 제 2 그룹 거리 평균으로 상기 제 1 그룹 거리 평균을 나누도록;
상기 평균 거리 비 측정을 임계값에 비교하도록; 및
상기 비교에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들의 최소의 것에 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하도록
구성되는,
비주얼 탐색을 수행하기 위한 장치.22. The method of claim 21,
The feature matching unit further comprises:
Compute two or more averages of the computed distances determined to be within the first group to produce a first group distance average;
Compute an average of the computed distances determined to be within the second group to produce a second group distance average;
Divide the first group distance average by the second group distance average to produce an average distance ratio measurement;
Compare the average distance ratio measurement to a threshold; And
Based on the comparison to determine if the query feature descriptor matches one of a plurality of reference feature descriptors associated with the minimum of the computed distances.
Configured,
Device for performing visual navigation.
상기 특징 매칭 유닛은 추가로,
기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하도록;
상기 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트(vote)를 할당하도록;
할당된 보트에 기초하여 상기 기준 영상들을 순서화하도록; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴(return)하도록
구성되는,
비주얼 탐색을 수행하기 위한 장치.22. The method of claim 21,
The feature matching unit further comprises:
A reference such that the computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images include reference images associated with those of the plurality of reference feature descriptors computed for the corresponding group of reference feature descriptors. Determine a unique group of images;
Assign a bot to each of the reference images determined to be in a unique group of the reference images;
To order the reference images based on the assigned boat; And
To return ordered reference images in response to the visual search query.
Configured,
Device for performing visual navigation.
상기 특징 매칭 유닛은,
상기 기준 영상들 각각에 상수 보트를 할당하는 것;
상기 질의 특징 기술자와 상기 복수의 기준 특징 기술자들 중 최근접의 것 간의 컴퓨팅된 거리에 비견되는 대응하는 컴퓨팅된 거리의 거리 비에 비례하여 보트를 할당하는 것; 및
상기 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대로 순서화될 때 상기 제 1 그룹 내의 대응하는 컴퓨팅된 거리의 랭크(rank)에 비례하여 보트를 할당하는 것 중 하나 이상에 의해 상기 보트를 할당하도록
구성되는,
비주얼 탐색을 수행하기 위한 장치.25. The method of claim 24,
The feature matching unit,
Assigning a constant boat to each of the reference images;
Assigning a boat in proportion to a distance ratio of a corresponding computed distance that is comparable to a computed distance between the query feature descriptor and the nearest one of the plurality of reference feature descriptors; And
To allocate the boat by one or more of allocating the boat in proportion to the rank of the corresponding computed distance in the first group when the computed distances of the first group are ordered from minimum to maximum.
Configured,
Device for performing visual navigation.
상기 질의 특징 기술자는 상기 비주얼 탐색 질의에 의해 제공되고 비주얼 탐색 알고리즘에 따라 질의 영상 데이터로부터 추출된 복수의 질의 특징 기술자들 중 하나를 포함하고,
상기 특징 매칭 유닛은 추가로,
상기 복수의 질의 특징 기술자들 각각에 대해, 컴퓨팅된 복수의 거리들을 생성하기 위해 상기 복수의 질의 특징 기술자들 중 현재의 것과 상기 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하도록;
상기 복수의 거리들 각각에 대해, 상기 클러스터링 알고리즘에 따라 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹을 결정하도록 - 상기 컴퓨팅된 복수의 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 그룹들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고, 상기 컴퓨팅된 복수의 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 복수의 질의 특징 기술자들 중 현재의 것으로부터 떨어져 있다고 표시하는 컴퓨팅된 복수의 거리들의 것들을 포함함 - ; 및
상기 복수의 질의 특징 기술자들 각각이 상기 컴퓨팅된 복수의 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹에 기초하여 상기 컴퓨팅된 복수의 거리들의 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하도록
구성되는,
비주얼 탐색을 수행하기 위한 장치.22. The method of claim 21,
The query feature descriptor includes one of a plurality of query feature descriptors provided by the visual search query and extracted from query image data according to a visual search algorithm,
The feature matching unit further comprises:
For each of the plurality of query feature descriptors, compute a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to produce a plurality of computed distances;
For each of the plurality of distances, to determine a first group of the computed plurality of distances and a second group of the computed plurality of distances according to the clustering algorithm—the first group of computed plurality of distances is The associated of the plurality of reference feature descriptors include those of computed distances indicating that the query feature descriptor is near relative to those of the computed plurality of distances determined to be within the second group of the computed plurality of groups; Wherein the second group of computed plurality of distances is compared to those of the computed plurality of distances that are associated with the plurality of reference feature descriptors within the first group of computed plurality of distances. Computing that indicates that you are away from the current one Includes those of a plurality of distances; And
Each of the plurality of query feature descriptors associated with a minimum of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances. To determine if it matches one of
Configured,
Device for performing visual navigation.
상기 특징 매칭 유닛은 추가로,
상기 복수의 질의 특징 기술자들 각각에 대해, 기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하도록;
상기 복수의 질의 특징 기술자들 각각에 대해 결정된 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당하도록;
상기 복수의 질의 특징 기술자들 각각에 대해 보트들을 할당한 이후, 할당된 보트들에 기초하여 상기 기준 영상들을 순서화하도록
구성되고,
상기 인터페이스는 상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴하는,
비주얼 탐색을 수행하기 위한 장치.27. The method of claim 26,
The feature matching unit further comprises:
For each of the plurality of query feature descriptors, the plurality of computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images are computed for the corresponding group of reference feature descriptors. Determine a unique group of reference images to include reference images associated with those of the reference feature descriptors;
Assign a boat to each of the reference images determined to be in a unique group of reference images determined for each of the plurality of query feature descriptors;
After allocating boats for each of the plurality of query feature descriptors, order the reference images based on the assigned boats.
Respectively,
The interface returns ordered reference images in response to the visual search query,
Device for performing visual navigation.
상기 질의 특징 기술자는,
로컬 특징-기반 비주얼 탐색 알고리즘에 따라 질의 영상으로부터 추출되는,
비주얼 탐색을 수행하기 위한 장치.22. The method of claim 21,
The feature descriptor of the above quality,
Extracted from the query image according to a local feature-based visual search algorithm,
Device for performing visual navigation.
상기 로컬-특징 기반 비주얼 탐색 알고리즘은,
SIFT(scale invariant feature transform) 알고리즘을 포함하는,
비주얼 탐색을 수행하기 위한 장치.29. The method of claim 28,
The local-feature based visual search algorithm,
Including a scale invariant feature transform (SIFT) algorithm,
Device for performing visual navigation.
상기 인터페이스는,
클라이언트 디바이스로부터 압축된 질의 특징 기술자로서 상기 질의 특징 기술자를 수신하도록 구성되고,
상기 장치는,
비주얼 탐색 디바이스를 통해 상기 압축된 질의 특징 기술자로부터 상기 질의 특징 기술자를 재구성하도록 구성되는 특징 재구성 유닛을 포함하는,
비주얼 탐색을 수행하기 위한 장치. 22. The method of claim 21,
The interface is,
Receive the query feature descriptor as a compressed query feature descriptor from a client device,
The apparatus comprises:
A feature reconstruction unit configured to reconstruct the query feature descriptor from the compressed query feature descriptor via a visual search device,
Device for performing visual navigation.
상기 명령은 실행될 때, 하나 이상의 프로세서들로 하여금,
비주얼 탐색 질의에 의해 제공된 질의 특징 기술자(query feature descriptor)와 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하게 하고 - 상기 비주얼 탐색 질의는 상기 비주얼 탐색을 개시함 - ; 및
클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하게 하고 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및
상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하게 하는
컴퓨터-판독 가능한 매체.A computer-readable medium containing instructions,
When executed, the instruction causes one or more processors to:
Compute a distance between each of a plurality of reference feature descriptors and a query feature descriptor provided by a visual search query, wherein the visual search query initiates the visual search; And
Determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is associated with the plurality of reference feature descriptors. And those of computed distances indicating that they are near to the query feature descriptor as compared to those of the computed distances determined to be within a second group of calculated distances, wherein the second group of computed distances includes Includes those of computed distances indicating that an association is away from the query feature descriptor relative to those of computed distances determined to be within one or more first groups of computed distances; And
And based on the determined first group of computed distances and the second group of computed distances, determine that the query feature descriptor matches one of a plurality of reference feature descriptors associated with the least of the computed distances. doing
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
k-평균 클러스터링 알고리즘(k-means clustering algorithm), 가우시안 피팅 알고리즘(Gaussian fitting algorithm) 및 그래픽 컷팅 알고리즘(graph cutting algorithm) 중 하나 이상에 따라 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹을 결정하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 31, wherein
When executed, causes the one or more processors to:
one or more first groups of computed distances and the computed distances according to one or more of a k-means clustering algorithm, a Gaussian fitting algorithm, and a graph cutting algorithm Instructions to determine a second group of characters
≪ / RTI >
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
제 1 그룹 거리 평균을 생성하기 위해 상기 제 1 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 2개 이상의 평균을 컴퓨팅하게 하고;
제 2 그룹 거리 평균을 생성하기 위해 상기 제 2 그룹 내에 있는 것으로 결정된 상기 컴퓨팅된 거리들의 평균을 컴퓨팅하게 하고;
평균 거리 비 측정을 생성하기 위해 상기 제 2 그룹 거리 평균으로 상기 제 1 그룹 거리 평균을 나누게 하고;
상기 평균 거리 비 측정을 임계값에 비교하게 하고; 및
상기 비교에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들의 최소의 것에 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 31, wherein
When executed, causes the one or more processors to:
Compute two or more averages of the computed distances determined to be within the first group to produce a first group distance average;
Compute an average of the computed distances determined to be within the second group to produce a second group distance average;
Divide the first group distance average by the second group distance average to produce an average distance ratio measurement;
Compare the average distance ratio measurement to a threshold; And
Instructions that, based on the comparison, cause the query feature descriptor to match one of a plurality of reference feature descriptors associated with the minimum of the computed distances.
≪ / RTI >
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하게 하고;
상기 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트(vote)를 할당하게 하고;
할당된 보트에 기초하여 상기 기준 영상들을 순서화하게 하고; 및
상기 비주얼 탐색 질의에 응답하여 순서화된 기준 영상들을 리턴(return)하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 31, wherein
When executed, causes the one or more processors to:
A reference such that the computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images include reference images associated with those of the plurality of reference feature descriptors computed for the corresponding group of reference feature descriptors. Determine a unique group of images;
Assign a bot to each of the reference images determined to be in a unique group of the reference images;
Order the reference images based on the assigned boat; And
Instructions to return ordered reference images in response to the visual search query
≪ / RTI >
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
상기 기준 영상들 각각에 상수 보트를 할당하게 하고
상기 질의 특징 기술자와 상기 복수의 기준 특징 기술자들 중 최근접의 것 간의 컴퓨팅된 거리에 비견되는 대응하는 컴퓨팅된 거리의 거리 비에 비례하여 보트를 할당하게 하고; 및
상기 제 1 그룹의 컴퓨팅된 거리들이 최소로부터 최대로 순서화될 때 상기 제 1 그룹 내의 대응하는 컴퓨팅된 거리의 랭크(rank)에 비례하여 보트를 할당하는 것 중 하나 이상에 의해 상기 보트를 할당하게 하는 명령들을
더 포함하는,
컴퓨터-판독 가능한 매체.35. The method of claim 34,
When executed, causes the one or more processors to:
Assign a constant boat to each of the reference images
Assign a boat in proportion to a distance ratio of a corresponding computed distance that is comparable to a computed distance between the query feature descriptor and the nearest one of the plurality of reference feature descriptors; And
Assigning the boat by one or more of allocating the boat in proportion to the rank of the corresponding computed distance in the first group when the computed distances of the first group are ordered from minimum to maximum. Commands
Further included,
Computer-readable medium.
상기 질의 특징 기술자는 상기 비주얼 탐색 질의에 의해 제공되고 비주얼 탐색 알고리즘에 따라 질의 영상 데이터로부터 추출된 복수의 질의 특징 기술자들 중 하나를 포함하고,
상기 컴퓨터-판독 가능한 매체는 실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
상기 복수의 질의 특징 기술자들 각각에 대해, 컴퓨팅된 복수의 거리들을 생성하기 위해 상기 복수의 질의 특징 기술자들 중 현재의 것과 상기 복수의 기준 특징 기술자들 각각 간의 거리를 컴퓨팅하게 하고;
상기 복수의 거리들 각각에 대해, 상기 클러스터링 알고리즘에 따라 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹을 결정하게 하고 - 상기 컴퓨팅된 복수의 거리들의 제 1 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 그룹들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고, 상기 컴퓨팅된 복수의 거리들의 제 2 그룹은 상기 복수의 기준 특징 기술자들의 연관된 것이 상기 컴퓨팅된 복수의 거리들의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들의 것들에 비해 상기 복수의 질의 특징 기술자들 중 현재의 것으로부터 떨어져 있다고 표시하는 컴퓨팅된 복수의 거리들의 것들을 포함함 - ; 및
상기 복수의 질의 특징 기술자들 각각이 상기 컴퓨팅된 복수의 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 복수의 거리들의 제 2 그룹에 기초하여 상기 컴퓨팅된 복수의 거리들의 최소의 것과 연관된 복수의 기준 특징 기술자들 중 하나에 매칭하는지를 결정하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 31, wherein
The query feature descriptor includes one of a plurality of query feature descriptors provided by the visual search query and extracted from query image data according to a visual search algorithm,
The computer-readable medium, when executed, causes the one or more processors to:
For each of the plurality of query feature descriptors, compute a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to produce a plurality of computed distances;
For each of the plurality of distances, determine, according to the clustering algorithm, a first group of the computed plurality of distances and a second group of the computed plurality of distances-a first group of the computed plurality of distances Includes those of computed distances indicating that the associated of the plurality of reference feature descriptors is near to the query feature descriptor relative to those of the computed plurality of distances determined to be within the second group of the computed plurality of groups. And wherein the second group of computed plurality of distances is associated with the plurality of query features relative to those of the computed plurality of distances that are associated with the plurality of reference feature descriptors within a first group of the computed plurality of distances. The com which marks the engineer as being separated from the current one Tingdoen including ones of the plurality of distances; And
Each of the plurality of query feature descriptors associated with a minimum of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances. Instructions to determine whether to match one of the
≪ / RTI >
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
상기 복수의 질의 특징 기술자들 각각에 대해, 기준 영상들의 세트가 중복 기준 영상들을 포함하지 않도록 상기 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 복수의 거리들이 기준 특징 기술자들의 대응하는 그룹에 대해 컴퓨팅된 복수의 기준 특징 기술자들의 것들과 연관된 기준 영상들을 포함하도록 기준 영상들의 고유한 그룹을 결정하게 하고;
상기 복수의 질의 특징 기술자들 각각에 대해 결정된 기준 영상들의 고유한 그룹 내에 있는 것으로 결정된 기준 영상들 각각에 보트를 할당하게 하고;
상기 복수의 질의 특징 기술자들 각각에 대해 보트들을 할당한 이후, 할당된 보트들에 기초하여 상기 기준 영상들을 순서화하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 36,
When executed, causes the one or more processors to:
For each of the plurality of query feature descriptors, the plurality of computed distances determined to be within the first group such that the set of reference images does not include duplicate reference images are computed for the corresponding group of reference feature descriptors. Determine a unique group of reference images to include reference images associated with those of the reference feature descriptors;
Assign a boat to each of the reference images determined to be in a unique group of reference images determined for each of the plurality of query feature descriptors;
Instructions for assigning boats for each of the plurality of query feature descriptors, and then ordering the reference images based on the assigned boats
≪ / RTI >
Computer-readable medium.
상기 질의 특징 기술자는,
로컬 특징-기반 비주얼 탐색 알고리즘에 따라 질의 영상으로부터 추출되는,
컴퓨터-판독 가능한 매체.The method of claim 31, wherein
The feature descriptor of the above quality,
Extracted from the query image according to a local feature-based visual search algorithm,
Computer-readable medium.
상기 로컬-특징 기반 비주얼 탐색 알고리즘은,
SIFT(scale invariant feature transform) 알고리즘을 포함하는,
컴퓨터-판독 가능한 매체.The method of claim 38,
The local-feature based visual search algorithm,
Including a scale invariant feature transform (SIFT) algorithm,
Computer-readable medium.
실행 될 때, 상기 하나 이상의 프로세서들로 하여금,
클라이언트 디바이스로부터 비주얼 탐색 디바이스의 인터페이스를 통해 압축된 질의 특징 기술자로서 상기 질의 특징 기술자를 수신하게 하고; 및
상기 비주얼 탐색 디바이스를 통해 상기 압축된 질의 특징 기술자로부터 상기 질의 특징 기술자를 재구성하게 하는 명령들
을 더 포함하는,
컴퓨터-판독 가능한 매체. The method of claim 31, wherein
When executed, causes the one or more processors to:
Receive the query feature descriptor as a compressed query feature descriptor from a client device through an interface of a visual search device; And
Instructions to reconstruct the query feature descriptor from the compressed query feature descriptor via the visual search device
≪ / RTI >
Computer-readable medium.
하나 이상의 클라이언트 디바이스로부터 수신된 정보를 수신하기 위한 입력 - 상기 정보는 비주얼 탐색을 개시하기 위한 질의 특징 기술자를 포함함 - ;
복수의 기준 질의 기술자들을 나타내는 정보를 포함하는 데이터베이스; 및
상기 비주얼 탐색을 수행하도록 구성된 비주얼 탐색 서버 디바이스
를 포함하고,
상기 비주얼 탐색 서버 디바이스는,
상기 질의 특징 기술자를 수신하기 위한 인터페이스; 및
특징 매칭 유닛
을 포함하고,
상기 특징 매칭 유닛은,
상기 질의 특징 기술자와 상기 복수의 기준 질의 기술자들 각각 간의 거리를 컴퓨팅하도록;
클러스터링 알고리즘(clustering algorithm)에 따라 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 및 컴퓨팅된 거리들의 제 2 그룹을 결정하도록 - 상기 컴퓨팅된 거리들의 제 1 그룹은 상기 복수의 기준 질의 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 제 2 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자에 대해 근처에 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함하고 컴퓨팅된 거리들의 제 2 그룹은 상기 복수의 기준 질의 기술자들의 연관된 것이 상기 컴퓨팅된 거리들의 하나 이상의 제 1 그룹 내에 있는 것으로 결정된 컴퓨팅된 거리들의 것들에 비해 상기 질의 특징 기술자로부터 떨어져 있다고 표시하는 컴퓨팅된 거리들의 것들을 포함함 - ; 및
상기 컴퓨팅된 거리들의 결정된 제 1 그룹 및 상기 컴퓨팅된 거리들의 제 2 그룹에 기초하여 상기 질의 특징 기술자가 상기 컴퓨팅된 거리들 중 최소의 것과 연관되는 복수의 기준 질의 기술자들 중 하나에 매칭하는지를 결정하도록 구성되는,
시스템.
As a system,
Input for receiving information received from one or more client devices, the information including a query feature descriptor for initiating a visual search;
A database containing information indicative of a plurality of reference query descriptors; And
A visual search server device configured to perform the visual search
Lt; / RTI >
The visual search server device,
An interface for receiving the query feature descriptor; And
Feature Matching Unit
/ RTI >
The feature matching unit,
Compute a distance between the query feature descriptor and each of the plurality of reference query descriptors;
Determine one or more first groups of computed distances and a second group of computed distances according to a clustering algorithm, wherein the first group of computed distances is associated with the plurality of reference query descriptors. And those of computed distances indicating that they are near to the query feature descriptor as compared to those of the computed distances determined to be within the second group of distances, wherein the second group of computed distances is associated with the plurality of reference query descriptors. Includes those of computed distances indicating that the one is farther from the query feature descriptor relative to those of the computed distances determined to be within the one or more first groups of computed distances; And
Based on the determined first group of computed distances and the second group of computed distances to determine whether the query feature descriptor matches one of a plurality of reference query descriptors associated with the least of the computed distances. Composed,
system.
Applications Claiming Priority (5)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US201161475428P | 2011-04-14 | 2011-04-14 | |
US61/475,428 | 2011-04-14 | ||
US13/312,335 US9036925B2 (en) | 2011-04-14 | 2011-12-06 | Robust feature matching for visual search |
US13/312,335 | 2011-12-06 | ||
PCT/US2012/033620 WO2012142483A1 (en) | 2011-04-14 | 2012-04-13 | Robust feature matching for visual search |
Publications (1)
Publication Number | Publication Date |
---|---|
KR20130142191A true KR20130142191A (en) | 2013-12-27 |
Family
ID=47006422
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
KR1020137030249A Abandoned KR20130142191A (en) | 2011-04-14 | 2012-04-13 | Robust feature matching for visual search |
Country Status (6)
Country | Link |
---|---|
US (1) | US9036925B2 (en) |
EP (1) | EP2697725A1 (en) |
JP (1) | JP5749394B2 (en) |
KR (1) | KR20130142191A (en) |
CN (1) | CN103582884A (en) |
WO (1) | WO2012142483A1 (en) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
KR20200114381A (en) * | 2019-03-28 | 2020-10-07 | 오스템임플란트 주식회사 | Method for automatically integrating scan models and imaging processing apparatus therefor |
Families Citing this family (40)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7565008B2 (en) | 2000-11-06 | 2009-07-21 | Evryx Technologies, Inc. | Data capture and identification system and process |
US8224078B2 (en) | 2000-11-06 | 2012-07-17 | Nant Holdings Ip, Llc | Image capture and identification system and process |
US9310892B2 (en) | 2000-11-06 | 2016-04-12 | Nant Holdings Ip, Llc | Object information derived from object images |
US7899243B2 (en) | 2000-11-06 | 2011-03-01 | Evryx Technologies, Inc. | Image capture and identification system and process |
US7680324B2 (en) | 2000-11-06 | 2010-03-16 | Evryx Technologies, Inc. | Use of image-derived information as search criteria for internet and other search engines |
US8625902B2 (en) * | 2010-07-30 | 2014-01-07 | Qualcomm Incorporated | Object recognition using incremental feature extraction |
US8706711B2 (en) | 2011-06-22 | 2014-04-22 | Qualcomm Incorporated | Descriptor storage and searches of k-dimensional trees |
TWI446276B (en) * | 2011-09-14 | 2014-07-21 | Ind Tech Res Inst | Apparatus and method for processing image fearure descriptor |
KR101912748B1 (en) * | 2012-02-28 | 2018-10-30 | 한국전자통신연구원 | Scalable Feature Descriptor Extraction and Matching method and system |
KR101904203B1 (en) * | 2012-06-20 | 2018-10-05 | 삼성전자주식회사 | Apparatus and method of extracting feature information of large source image using scalar invariant feature transform algorithm |
US9229983B2 (en) | 2012-11-30 | 2016-01-05 | Amazon Technologies, Inc. | System-wide query optimization |
US9846707B2 (en) | 2013-01-31 | 2017-12-19 | Bluebeam, Inc. | Method for color and size based pre-filtering for visual object searching of documents |
WO2014198055A1 (en) * | 2013-06-14 | 2014-12-18 | Intel Corporation | Image processing including adjoin feature based object detection, and/or bilateral symmetric object segmentation |
US10083368B2 (en) | 2014-01-28 | 2018-09-25 | Qualcomm Incorporated | Incremental learning for dynamic feature database management in an object recognition system |
US10043112B2 (en) * | 2014-03-07 | 2018-08-07 | Qualcomm Incorporated | Photo management |
KR101581112B1 (en) * | 2014-03-26 | 2015-12-30 | 포항공과대학교 산학협력단 | Method for generating hierarchical structured pattern-based descriptor and method for recognizing object using the descriptor and device therefor |
US9235215B2 (en) * | 2014-04-03 | 2016-01-12 | Honeywell International Inc. | Feature set optimization in vision-based positioning |
US9875301B2 (en) | 2014-04-30 | 2018-01-23 | Microsoft Technology Licensing, Llc | Learning multimedia semantics from large-scale unstructured data |
CN106716450B (en) * | 2014-05-06 | 2020-05-19 | 河谷控股Ip有限责任公司 | Image-Based Feature Detection Using Edge Vectors |
WO2015197029A1 (en) * | 2014-06-27 | 2015-12-30 | 北京奇虎科技有限公司 | Human face similarity recognition method and system |
US20160012594A1 (en) * | 2014-07-10 | 2016-01-14 | Ditto Labs, Inc. | Systems, Methods, And Devices For Image Matching And Object Recognition In Images Using Textures |
US10289910B1 (en) * | 2014-07-10 | 2019-05-14 | Hrl Laboratories, Llc | System and method for performing real-time video object recognition utilizing convolutional neural networks |
US9697233B2 (en) * | 2014-08-12 | 2017-07-04 | Paypal, Inc. | Image processing and matching |
US20160117632A1 (en) * | 2014-10-23 | 2016-04-28 | Toshiba Tec Kabushiki Kaisha | Information processing apparatus, commodity sales system, and commodity sales method |
US10013637B2 (en) | 2015-01-22 | 2018-07-03 | Microsoft Technology Licensing, Llc | Optimizing multi-class image classification using patch features |
US9785866B2 (en) | 2015-01-22 | 2017-10-10 | Microsoft Technology Licensing, Llc | Optimizing multi-class multimedia data classification using negative data |
US10510038B2 (en) * | 2015-06-17 | 2019-12-17 | Tata Consultancy Services Limited | Computer implemented system and method for recognizing and counting products within images |
CN106295489B (en) | 2015-06-29 | 2021-09-28 | 株式会社日立制作所 | Information processing method, information processing device and video monitoring system |
US10424003B2 (en) * | 2015-09-04 | 2019-09-24 | Accenture Global Solutions Limited | Management of physical items based on user analytics |
US20170323149A1 (en) * | 2016-05-05 | 2017-11-09 | International Business Machines Corporation | Rotation invariant object detection |
US10097865B2 (en) | 2016-05-12 | 2018-10-09 | Arris Enterprises Llc | Generating synthetic frame features for sentinel frame matching |
US11256923B2 (en) | 2016-05-12 | 2022-02-22 | Arris Enterprises Llc | Detecting sentinel frames in video delivery using a pattern analysis |
CN107529071B (en) * | 2016-06-22 | 2019-03-01 | 腾讯科技(深圳)有限公司 | A kind of video data handling procedure and device |
CN108830283B (en) * | 2018-06-15 | 2020-10-20 | 阿依瓦(北京)技术有限公司 | Image feature point matching method |
US10878037B2 (en) | 2018-06-21 | 2020-12-29 | Google Llc | Digital supplement association and retrieval for visual search |
JP7393361B2 (en) * | 2018-06-21 | 2023-12-06 | グーグル エルエルシー | Digital supplementary association and search for visual search |
CN110059214B (en) * | 2019-04-01 | 2021-12-14 | 北京奇艺世纪科技有限公司 | Image resource processing method and device |
AU2020289853B2 (en) * | 2020-04-09 | 2022-02-03 | Sensetime International Pte. Ltd. | Matching method and apparatus, electronic device, computer-readable storage medium, and computer program |
CN111522986B (en) * | 2020-04-23 | 2023-10-10 | 北京百度网讯科技有限公司 | Image retrieval methods, devices, equipment and media |
WO2025095865A1 (en) * | 2023-11-02 | 2025-05-08 | Nanyang Technological University | Binary feature matching methods and systems |
Family Cites Families (60)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US6400996B1 (en) | 1999-02-01 | 2002-06-04 | Steven M. Hoffberg | Adaptive pattern recognition based control system and method |
US6819783B2 (en) * | 1996-09-04 | 2004-11-16 | Centerframe, Llc | Obtaining person-specific images in a public venue |
US5819258A (en) | 1997-03-07 | 1998-10-06 | Digital Equipment Corporation | Method and apparatus for automatically generating hierarchical categories from large document collections |
US6134541A (en) | 1997-10-31 | 2000-10-17 | International Business Machines Corporation | Searching multidimensional indexes using associated clustering and dimension reduction information |
US6512850B2 (en) | 1998-12-09 | 2003-01-28 | International Business Machines Corporation | Method of and apparatus for identifying subsets of interrelated image objects from a set of image objects |
US6347313B1 (en) | 1999-03-01 | 2002-02-12 | Hewlett-Packard Company | Information embedding based on user relevance feedback for object retrieval |
US6711293B1 (en) | 1999-03-08 | 2004-03-23 | The University Of British Columbia | Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image |
JP2001005967A (en) | 1999-06-21 | 2001-01-12 | Matsushita Electric Ind Co Ltd | Image transmitting device and neural network |
US6446068B1 (en) | 1999-11-15 | 2002-09-03 | Chris Alan Kortge | System and method of finding near neighbors in large metric space databases |
JP3550681B2 (en) | 1999-12-10 | 2004-08-04 | 日本電気株式会社 | Image search apparatus and method, and storage medium storing similar image search program |
JP2002007432A (en) | 2000-06-23 | 2002-01-11 | Ntt Docomo Inc | Information retrieval system |
CN100392749C (en) | 2000-09-08 | 2008-06-04 | 皇家菲利浦电子有限公司 | Apparatus for reproducing information signal stored on storage medium |
US7113980B2 (en) | 2001-09-06 | 2006-09-26 | Bea Systems, Inc. | Exactly once JMS communication |
JP3860046B2 (en) | 2002-02-15 | 2006-12-20 | インターナショナル・ビジネス・マシーンズ・コーポレーション | Program, system and recording medium for information processing using random sample hierarchical structure |
CA2388358A1 (en) | 2002-05-31 | 2003-11-30 | Voiceage Corporation | A method and device for multi-rate lattice vector quantization |
US6931413B2 (en) | 2002-06-25 | 2005-08-16 | Microsoft Corporation | System and method providing automated margin tree analysis and processing of sampled data |
DE60233935D1 (en) | 2002-07-19 | 2009-11-19 | Mitsubishi Electric Inf Tech | Method and device for data processing |
KR20020081189A (en) | 2002-10-01 | 2002-10-26 | (주)엠바이오시스 | Sample transfer system by multi-tube and vacuum chamber |
JP4105704B2 (en) | 2004-05-18 | 2008-06-25 | シャープ株式会社 | Image processing apparatus, image forming apparatus, image processing method, program, and recording medium |
US7161507B2 (en) | 2004-08-20 | 2007-01-09 | 1St Works Corporation | Fast, practically optimal entropy coding |
US8276088B2 (en) | 2007-07-11 | 2012-09-25 | Ricoh Co., Ltd. | User interface for three-dimensional navigation |
US7447362B2 (en) | 2004-11-08 | 2008-11-04 | Dspv, Ltd. | System and method of enabling a cellular/wireless device with imaging capabilities to decode printed alphanumeric characters |
GB2437428A (en) | 2004-12-06 | 2007-10-24 | Dspv Ltd | System and method for generic symbol recognition and user authenication using a communication device with imaging capabilities |
US20060164682A1 (en) | 2005-01-25 | 2006-07-27 | Dspv, Ltd. | System and method of improving the legibility and applicability of document pictures using form based image enhancement |
GB2438777A (en) | 2005-02-15 | 2007-12-05 | Dspv Ltd | System and method of user interface and data entry from a video call |
US8036497B2 (en) | 2005-03-01 | 2011-10-11 | Osaka Prefecture University Public Corporation | Method, program and apparatus for storing document and/or image using invariant values calculated from feature points and method, program and apparatus for retrieving document based on stored document and/or image |
US7657100B2 (en) | 2005-05-09 | 2010-02-02 | Like.Com | System and method for enabling image recognition and searching of images |
WO2007052171A2 (en) | 2005-09-01 | 2007-05-10 | Zvi Haim Lev | System and method for reliable content access using a cellular/wireless device with imaging capabilities |
US20070250851A1 (en) | 2005-10-18 | 2007-10-25 | Lev Zvi H | System and method for identity verification and access control using a cellular/wireless device with audiovisual playback capabilities |
US20090017765A1 (en) | 2005-11-04 | 2009-01-15 | Dspv, Ltd | System and Method of Enabling a Cellular/Wireless Device with Imaging Capabilities to Decode Printed Alphanumeric Characters |
US7539657B1 (en) | 2005-11-12 | 2009-05-26 | Google Inc. | Building parallel hybrid spill trees to facilitate parallel nearest-neighbor matching operations |
US7725484B2 (en) | 2005-11-18 | 2010-05-25 | University Of Kentucky Research Foundation (Ukrf) | Scalable object recognition using hierarchical quantization with a vocabulary tree |
CN100418092C (en) | 2006-02-20 | 2008-09-10 | 南京联创科技股份有限公司 | Grid and T-tree index method for rapid positioning in main memory database |
US7860317B2 (en) | 2006-04-04 | 2010-12-28 | Microsoft Corporation | Generating search results based on duplicate image detection |
US7623683B2 (en) | 2006-04-13 | 2009-11-24 | Hewlett-Packard Development Company, L.P. | Combining multiple exposure images to increase dynamic range |
US20080034396A1 (en) | 2006-05-30 | 2008-02-07 | Lev Zvi H | System and method for video distribution and billing |
US8031914B2 (en) | 2006-10-11 | 2011-10-04 | Hewlett-Packard Development Company, L.P. | Face-based image clustering |
WO2008100248A2 (en) | 2007-02-13 | 2008-08-21 | Olympus Corporation | Feature matching method |
US7903883B2 (en) | 2007-03-30 | 2011-03-08 | Microsoft Corporation | Local bi-gram model for object recognition |
KR100911628B1 (en) | 2007-06-19 | 2009-08-12 | 서강대학교산학협력단 | How to refine image search results based on text queries |
US20090132487A1 (en) | 2007-11-21 | 2009-05-21 | Zvi Haim Lev | System and method for video call based content retrieval, directory and web access services |
EP2272014A2 (en) | 2008-04-29 | 2011-01-12 | LTU Technologies S.A.S. | Method for generating a representation of image content using image search and retrieval criteria |
WO2009133855A1 (en) | 2008-04-30 | 2009-11-05 | 公立大学法人大阪府立大学 | Method of creating three-dimensional object identifying image database, processing apparatus and processing program |
JP5318503B2 (en) | 2008-09-02 | 2013-10-16 | ヤフー株式会社 | Image search device |
US8217952B2 (en) | 2008-11-26 | 2012-07-10 | Novell, Inc. | Techniques for caching images |
US8818103B2 (en) | 2009-03-04 | 2014-08-26 | Osaka Prefecture University Public Corporation | Image retrieval method, image retrieval program, and image registration method |
JP2010250658A (en) | 2009-04-17 | 2010-11-04 | Seiko Epson Corp | Printing apparatus, image processing apparatus, image processing method, and computer program |
US20100303354A1 (en) | 2009-06-01 | 2010-12-02 | Qualcomm Incorporated | Efficient coding of probability distributions for image feature descriptors |
US20100310174A1 (en) | 2009-06-05 | 2010-12-09 | Qualcomm Incorporated | Efficient incremental coding of probability distributions for image feature descriptors |
JP5164222B2 (en) | 2009-06-25 | 2013-03-21 | Kddi株式会社 | Image search method and system |
US8605956B2 (en) * | 2009-11-18 | 2013-12-10 | Google Inc. | Automatically mining person models of celebrities for visual search applications |
US8949252B2 (en) | 2010-03-29 | 2015-02-03 | Ebay Inc. | Product category optimization for image similarity searching of image-based listings in a network-based publication system |
US8548255B2 (en) * | 2010-04-15 | 2013-10-01 | Nokia Corporation | Method and apparatus for visual search stability |
US8625902B2 (en) | 2010-07-30 | 2014-01-07 | Qualcomm Incorporated | Object recognition using incremental feature extraction |
US20130132377A1 (en) * | 2010-08-26 | 2013-05-23 | Zhe Lin | Systems and Methods for Localized Bag-of-Features Retrieval |
US20120110025A1 (en) | 2010-10-28 | 2012-05-03 | Qualcomm Incorporated | Coding order-independent collections of words |
US8645380B2 (en) | 2010-11-05 | 2014-02-04 | Microsoft Corporation | Optimized KD-tree for scalable search |
US8706711B2 (en) | 2011-06-22 | 2014-04-22 | Qualcomm Incorporated | Descriptor storage and searches of k-dimensional trees |
US8798362B2 (en) * | 2011-08-15 | 2014-08-05 | Hewlett-Packard Development Company, L.P. | Clothing search in images |
EP2780861A1 (en) | 2011-11-18 | 2014-09-24 | Metaio GmbH | Method of matching image features with reference features and integrated circuit therefor |
-
2011
- 2011-12-06 US US13/312,335 patent/US9036925B2/en not_active Expired - Fee Related
-
2012
- 2012-04-13 WO PCT/US2012/033620 patent/WO2012142483A1/en active Application Filing
- 2012-04-13 CN CN201280018354.8A patent/CN103582884A/en active Pending
- 2012-04-13 JP JP2014505360A patent/JP5749394B2/en not_active Expired - Fee Related
- 2012-04-13 KR KR1020137030249A patent/KR20130142191A/en not_active Abandoned
- 2012-04-13 EP EP12718803.5A patent/EP2697725A1/en not_active Withdrawn
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
KR20200114381A (en) * | 2019-03-28 | 2020-10-07 | 오스템임플란트 주식회사 | Method for automatically integrating scan models and imaging processing apparatus therefor |
Also Published As
Publication number | Publication date |
---|---|
US20120263388A1 (en) | 2012-10-18 |
JP2014512057A (en) | 2014-05-19 |
WO2012142483A1 (en) | 2012-10-18 |
JP5749394B2 (en) | 2015-07-15 |
CN103582884A (en) | 2014-02-12 |
US9036925B2 (en) | 2015-05-19 |
EP2697725A1 (en) | 2014-02-19 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US9036925B2 (en) | Robust feature matching for visual search | |
Noh et al. | Large-scale image retrieval with attentive deep local features | |
JP5654127B2 (en) | Object recognition using incremental feature extraction | |
Kandaswamy et al. | Efficient texture analysis of SAR imagery | |
EP2805262B1 (en) | Image index generation based on similarities of image features | |
CN102254015B (en) | Image retrieval method based on visual phrases | |
KR101420550B1 (en) | Methods, devices and computer-readable storage media for fast subspace projection of descriptor patches for image recognition | |
Raza et al. | Correlated primary visual texton histogram features for content base image retrieval | |
JP5607261B2 (en) | System and method for improving feature generation in object recognition | |
GB2516037A (en) | Compact and robust signature for large scale visual search, retrieval and classification | |
JP2013025799A (en) | Image search method, system, and program | |
KR101912748B1 (en) | Scalable Feature Descriptor Extraction and Matching method and system | |
CN116457776A (en) | Image processing method, device, computing device and medium | |
CN103064857B (en) | Image inquiry method and image querying equipment | |
Kim et al. | Classification and indexing scheme of large-scale image repository for spatio-temporal landmark recognition | |
Parseh et al. | Semantic-aware visual scene representation | |
CN107870923B (en) | Image retrieval method and device | |
Wu et al. | A vision-based indoor positioning method with high accuracy and efficiency based on self-optimized-ordered visual vocabulary | |
Nguyen et al. | Video instance search via spatial fusion of visual words and object proposals | |
WO2024027347A1 (en) | Content recognition method and apparatus, device, storage medium, and computer program product | |
Lahrache et al. | Bag‐of‐features for image memorability evaluation | |
CN114973225B (en) | License plate identification method, device and equipment | |
안재현 et al. | Efficient Object-based Image Retrieval Method using Color Features from Salient Regions | |
CN120632147A (en) | Image searching method, device, storage medium and program product | |
Janet et al. | Index model for image retrieval using SIFT distortion |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A201 | Request for examination | ||
PA0105 | International application |
Patent event date: 20131114 Patent event code: PA01051R01D Comment text: International Patent Application |
|
PA0201 | Request for examination | ||
PG1501 | Laying open of application | ||
E902 | Notification of reason for refusal | ||
PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20140814 Patent event code: PE09021S01D |
|
E902 | Notification of reason for refusal | ||
PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20150415 Patent event code: PE09021S01D |
|
E701 | Decision to grant or registration of patent right | ||
PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 20151222 |
|
PC1904 | Unpaid initial registration fee |