使用特徵點來劃分區域的設備、方法、介質和移動機器人的製作方法

2023-04-25 07:17:06 2

專利名稱：使用特徵點來劃分區域的設備、方法、介質和移動機器人的製作方法
技術領域：
實施例涉及一種通過使用特徵點來劃分區域的設備、方法和介質以及使 用所述設備、方法和介質的移動機器人，更具體地講，涉及一種通過從特徵 點提取通路(gateway)的兩個端點來劃分區域的設備、方法和介質以及使用 所述設備、方法和介質的移動機器人。
背景技術：
通常，作為工業自動化的一部分，為工業目的開發了機器人以將其用於 重複操作。近年來，除了工業機器人，各種機器人(具體地講，在家庭或辦 公室中自己移動以代替人來工作的人性化的機器人)被投入實際使用。例如， 機器人包括機器人清潔器、安全機器人、嚮導機器人、服務機器人等。
在諸如機器人清潔器的移動機器人中，必須區分區域以進行打掃。例如， 在機器人清潔器中，如果用戶發出打掃區域(例如，房間、客廳和廚房)的 命令，則機器人清潔器應該能夠區分和識別房間、客廳和廚房以進行打掃。 為了執行這些操作，機器人應該能夠將整個空間正確地顯示為網格地圖，在 機器人中存儲的網格地圖應該被劃分成諸如房間和客廳的區域(拓樸地圖)， 以允許用戶發出打掃區域的命令。
作為劃分區域的方法，公知的方法有這樣一種方法將大門識別為劃分 區域的參考。公開了一種通過識別進口門來劃分房間的方法(例如，參看第 2005-211359號日本專利)，在這種方法中，機器人清潔器識別安裝在房間入 口的附近的路標，以在移動的同時通過使用傳感器和相機來檢測房門，從而 執行打掃。在這種方法中存在一些問題。應該為每個入口門安裝路標，這有 些麻煩。因此，如果入口門很多，則成本高。此外，如果改變打掃的空間， 則應該重新安裝^各標。圖1是順序地顯示通過用Voronoi圖檢測窄路徑來繪製拓樸地圖的方法 的示圖。首先，當在自由空間的所有網格中獲得障礙物之間的最短距離時， 通過連接最短距離的中心點來繪製Voronoi圖(圖1的(B))。 Voronoi圖的 每一點具有距障礙物的最短距離的值，在最短距離具有局部最小值的情況下， 當沿Voronoi圖定義X軸並將每一點到障礙物的距離定義為Y軸時，Voronoi 圖的點，即，具有局部最小值的Voronoi圖的點被確定為臨界點(圖1的(C))。 接著，通過連接距每一臨界點最短的點來繪製臨界線(圖1的(D))。這種 臨界線是通過Voronoi圖提取的窄路徑。由臨界線劃分的每一區域變成拓樸區 域(圖1的(E))。
在現有技術中，因為應該獲得從自由空間的所有網格到障礙物的最短距 離，所以需要大量計算。另外，由於實際的地圖有太多的不一致，所以產生 了不必要的臨界點，從而在拓樸地圖中產生了不期望的細微區域。
以下描述的示例性實施例克服了現有技術中存在的缺點，並提供通過從 特徵點檢測通路來劃分區域以降低計算量的設備、方法和介質。

發明內容
根據本發明的一方面，提供一種通過使用特徵點劃分區域的方法，所述 方法包括通過使用多個網格點形成網格地圖，其中，通過檢測與障礙物之 間的距離獲得所述網格點；從網格地圖提取特徵點；從特徵點提取包括在區 域劃分元素的範圍中的候選特徵點對；從候選特徵點對提取滿足區域劃分元 素的要求的最終特徵點對；通過將最終特徵點對彼此連接來形成臨界線；和 根據具有通過連接臨界線和網格地圖形成的閉合曲線的區域之間的大小關係 形成最終區域。
根據本發明的一方面，提供一種通過使用特徵點劃分區域的設備。所述 設備可包括網格地圖生成單元，通過使用多個網格點形成網格地圖，其中， 通過檢測與障礙物之間的距離獲得所述網格點；特徵點提取單元，從網格地 圖提取特徵點；候選特徵點對提取單元，從特徵點提取包括在區域劃分元素 的範圍之內的候選特徵點對；最終特徵點對提取單元，從候選特徵點對提取 滿足區域劃分元素的要求的最終特徵點對；臨界線形成單元，通過連接最終 特徵點來形成臨界線；和區域形成單元，根據連接臨界線和網格地圖的閉合 曲線形成的區域之間的大小關係形成最終區域。
根據本發明的 一方面，提供一種通過使用特徵點劃分區域的設備的機器
人。所述設備可包括網格地圖生成單元、特徵點提取單元、候選特徵點對 提取單元、最終特徵點對提取單元、臨界線形成單元、區域形成單元、拓樸 地圖繪製單元和顯示單元，當選擇在顯示裝置上可識別地顯示的拓樸地圖的 預定區域時，自動打掃所述區域。
根據本發明的一方面，提供一種具有通過使用特徵點劃分區域的設備的 機器人。所述設備包括網格地圖生成單元，通過使用多個網格點形成網格 地圖，其中，通過檢測與障礙物之間的距離獲得所述網格點；特徵點提取單 元，從網格地圖提取特徵點；候選特徵點對提取單元，從特徵點提取包括在 區域劃分元素的範圍之內的特徵點對；最終特徵點對提取單元，從候選特徵 點對提取滿足區域劃分元素的要求的最終特徵點對；臨界線形成單元，通過 連接最終特徵點對來形成臨界線；區域形成單元，根據連接臨界線和網格地 圖的閉合曲線形成的區域之間的大小關係形成最終區域；拓樸地圖形成單元， 基於最終區域形成拓樸地圖；和顯示單元，在顯示裝置上顯示拓樸地圖，其 中，當選擇在顯示裝置上可識別地顯示的拓樸地圖的預定區域時，自動打掃 所述區域。
根據另 一方面，提供了存儲實現實施例的方法的計算機可讀指令的至少 一種計算機可讀介質。


從下面結合附圖對本發明示例性實施例的描述，這些和/或其他方面、特 點和優點將變得清楚，並更容易理解，其中
圖1是順序地顯示通過用Voronoi圖檢測窄路徑來繪製拓樸地圖的方法的 示圖2是示出根據本發明示例性實施例的通過使用特徵點來劃分區域的方 法的流程圖3是示出根據本發明示例性實施例的通過使用網格點產生的網格地圖 以及從網格地圖中提取的特徵點的示圖4是根據本發明示例性實施例的提取最終特徵點對的圖2的操作S220 的詳細流程圖5A、圖5B和圖5C是基於對通路的要求從候選特徵點對中提取最終
特徵點對的圖3的部分A的放大示圖6A和圖6B是圖3的部分A的放大示圖，圖6A和圖6B顯示了通過
比較將連接候選特徵點的線和網格地圖30連接到房間的邊界形成的閉合曲
線的長度，從候選特徵點對中提取最終特徵點對的過程；
圖7是根據示例性實施例的形成區域的圖2的操作S240的詳細流程圖； 圖8A、圖8B和圖8C是顯示通過產生的臨界線來形成最終區域的過程
的示圖9是顯示4艮據示例性實施例的產生的拓樸地圖的示圖；和
圖10是根據示例性實施例的通過使用特徵點劃分區域的設備的框圖。
具體實施例方式
現在詳細闡述示例性實施例，其示例在附圖中示出，其中，相同的標號 始終表示相同的部件。以下通過參照附圖來描述示例性實施例以解釋本發明。
圖2是示出根據本發明示例性實施例的通過使用特徵點來劃分區域的方 法的流程圖。
根據該示例性實施例，通過使用特徵點來劃分區域的方法包括操作 SllO，產生網格地圖30;操作S120，從網格地圖30中提取特徵點40;操作 S210，從特徵點40中提取候選特徵點對；操作S220,從所述候選特徵點對 中提取具有通路特徵的最終特徵點對；操作S230,由所述最終特徵點對來產 生臨界線；和操作S240，刪除由臨界線生成的區域之間的一些臨界線，以產 生最終區域。
通過使用特徵點來劃分區域的方法還可包括S250，基於最終區域產生 拓樸地圖；和操作S260，在顯示裝置上顯示拓樸地圖。
在左邊的操作S100 (圖2)，產生網格地圖30,並提取特徵點40,以準 備檢測通路。在右邊的操作S200 (圖2)，從特徵點40中檢測通路，以最終 產生拓樸地圖。
例如，具有能夠檢測距障礙物的距離的一個或多個傳感器的機器人清潔 器在自由空間的整個區域中自主地移動，以檢測障礙物。在通常家庭用的移 動機器人的情況下，障礙物指的是一種結構，例如，建築物的內壁和家具。 然而，移動機器人還可在其他環境下使用，障礙物可包括其他結構。移動機 器人檢測距障礙物的距離，以獲得包括多個點的網格點。用於檢測距障礙物
的距離的傳感器可使用紅外線、雷射或超聲波，但是使用並不限於此，各種 方法可被實現。
由從在機器人行進的同時獲得的多個網格點中提取的外部線(external line)形成網格地圖30。因此，移動機器人可從由傳感器獲得的多個網格點 來產生網格地圖30。
從多個網格點和網格地圖30中提取特徵點40 (S120)，特徵點40指的 是建築物的內壁的角和/或結構的邊。
RANSAC(隨機採樣一致性)算法可被用於提取特徵點40。通過RANSAC 算法，從多個網格點中提取多個線，因此，通過使用線交叉的點來提取特徵 點40。
另外，通過使用SLAM (同時定位與地圖創建)算法，可提取特徵點40。 通過SLAM算法，基於距離傳感器獲得的特徵點和用於更新的機器人的編碼 器信息來假設移動機器人的位置和外圍地圖，從而產生包括特徵點的地圖。 在IEEE Transactions on Robotics and Automation的2001年6月第17巻第3 期的"i倉文 "A Solution to the Simultaneous Localization and Map Building Problem"中詳細/>開了 SLAM (同時定位和地圖創建)算法，因此將省略對
圖3是示出根據本發明示例性實施例的通過使用網格點產生的網格地圖 30以及從網格地圖30中提取的特徵點40的示圖。 以下，網格地圖表示由障礙物佔用的網格。
30以及從網格地圖30中提取的特徵點40的示圖。圖3 (左側)是顯示從網 格地圖30提取的特徵點40的示圖。如圖所示，大多數特徵點40存在於網格 地圖30上，具體地講，特徵點40存在於網格地圖30中線的端點相遇的角。
在從網格地圖30中提取特徵點40之後，從特徵點40中提取區域劃分元 素的範圍內包括的候選特徵點對(S210)。通常，將區域劃分成房間和客廳的 區域劃分元素可以是諸如入口門的通路。
從特徵點40中提取被假設為通路的兩個端點的候選特徵點對。由於通路 的兩個端點是邊，所以在提取期間它們被識別為特徵點40。例如，通路可以 是門，門通常具有恆定範圍內的大小。另外，在整個空間，門可具有一致的 大小。因此，如果從提取的特徵點40之間的距離來提取與門的寬度相應的特 徵點對，則候選特徵點對之一變成與通^各相應的特徵點對。
通常，當不包括框架時，作為通路的木製的門的大小如下(單位mm)。 2037至2040 (高)* 937至940 (寬)* 36 (厚度) 2037至2040 (高)* 837至840 (寬)* 36 (厚度) 2037至2040 (高)* 737至740 (寬)* 36 (厚度)。
因此，作為門(通路的示例)的候選的特徵點40之間的距離在最小73.7cm 至最大94.0cm的範圍內。因此，與門相應的特徵點對在73.7cm至94.0cm的 範圍內的特徵點對之中。
當產生了網格地圖30時，以恆定間隔形成網格點，從而可能正好在邊緣 點處沒有形成網格點。因此，特徵點40可能不指示準確的邊緣點。因此，期 望考慮因為網格點的間隔而產生的噪聲。在這方面，優選地，在考慮由於通 路(例如門)的寬度範圍內的網格點的間隔而產生的噪聲的範圍內來提取候 選特徵點對。例如，如果網格點的間隔是lcm,則可提取72.7cm到95.0cm 範圍內的特徵點對。因為可能存在這樣的通路，例如一般門寬度範圍之外的 門，所以可基於用戶直接輸入的寬度來提取候選特徵點對。
接著，在上述操作中的提取的候選特徵點對中提取滿足區域劃分元素的 要求的最終特徵點對(S220)。例如，如果區域劃分元素是入口門(作為通路 的示例)，門的兩邊連接到牆壁；因此，兩個邊被示出，以被連接到網格地圖 30的牆壁。另一方面，如果入口門被打開，則在入口門之間不存在障礙物， 因此，在網格地圖30中沒有示出入口門之間的空間。另外，通過連接指示入 口門的候選特徵點對的線和網格地圖30而形成的閉合曲線的長度應該具有 與房間的邊界長度實質相等的長度。從多個候選特徵點對中提取滿足區域劃 分元素的要求的特徵點對，以獲得最終特徵點對。
圖4是根據本發明示例性實施例的提取最終特徵點對的圖2的操作S220 的詳細流程圖。
如上所述，在通路(例如，入口門)之間不存在障礙物，在網格地圖30 中沒有示出入口門。因此，如果特徵點對的線與網格地圖30重疊，則因為重 疊的對不是指示入口的特徵點對，所以可從候選特徵點對中排除所述重疊的 特徵點對(S222)。當確定連接特徵點對的線與網格地圖30是否重疊時，優 選地，如果在它們之間可插入預定間隔，則確定所述線與網格地圖30重疊。 這是因為，可以不從網格地圖30提取特徵點40,並且特徵點40可不存在於
網格地圖30上。然而，由於從網格地圖30提取特徵點，所以即使特徵點位
於網格地圖30之外，特徵點也可能位於與網格地圖30非常相鄰的位置。在 下面的描述中，只要特徵點40位於與網格地圖30非常相鄰的位置，存在於 網格地圖30的邊上的特徵點40甚至沒有必要與網格地圖30重疊。
另外，如上所述，由於通路(例如，入口門)的兩個邊連接到牆壁，所 以在網格地圖30中沒有示出連接特徵點的線，但是每個特徵點對都連接到其 他的特徵點40，從而形成網格地圖30。因此，如果特徵點40與通路(例如， 入口門)相應，則特徵點對的每一點都應該存在於網格地圖30上。因此，如 果形成對的特徵點不存在於網格地圖30上，則從候選特徵點對中排除該對 (S224 )。
即使經過上述兩個操作(S222和S224 )之後，在候選特徵點對中還可能 存在作為不是用於指示通路(例如，入口門)的最終特徵點對的特徵點對。 通過連接候選特徵點對的線和網格地圖30而形成的閉合曲線的長度的總和 應該與房間邊界實質上相等。可定義房間邊界的範圍，以與整個自由空間的 大小成比例。例如，在45碎(面積單位)的住宅的情況下，標準房間的大小 在61112至701112的範圍內，其邊界在10m至40m的範圍內。因此，如果閉合 曲線的長度不在房間邊界的範圍內，則可被排除(S226)。用戶可直接輸入房 間的周長，從而可基於該長度從候選特徵點對中提取最終特徵點對。
參照圖5A、圖5B、圖5C、圖6A和圖6B,將舉例描述從候選特徵點對 中獲得最終特徵點對的過程。
圖5A、圖5B和圖5C是圖3的部分A的放大示圖，基於對大門的要求 從候選特徵點對中提取最終特徵點對。
在圖5A中示出基於入口門(1、 3、 5、 7、 9和11)(通路的示例)的寬 度從特徵點40提取的候選特徵點對。在下文中，候選特徵點對(l、 3、 5、 7、 9和11 )將由自己的標號表示，諸如特徵點對1、特徵點對3。
對於特徵點對1和特徵點對9，連接特徵點40的線與網格地圖30重疊。 因此，特徵點對1 -陂排除在如圖5B所示的最終特徵點對之外。其餘候選特徵 點對(3、 5、 7和11 )沒有與網格地圖30重疊。
當在圖5B中所示的特徵點對(3、 5、 7和11 )中考慮特徵點對3和特 徵點對5時，所述對中的一個特徵點遠離網格地圖30。因此，網格地圖30 不包括特徵點對3和特徵點對5的所有點。因此，因為所述對不滿足形成入
口門的特徵點40應該連接到牆壁的情況，所以特徵點對3和特徵點對5被排 除在最終特徵點對之外。網格地圖30包括其餘候選特徵點對(7和11 )的所 有特徵點40。
如參照圖5A、圖5B和圖5C所述，即使在經歷上述兩個操作之後如圖 6A所示，在候選特徵點對中還存在不是指示入口門的最終特徵點對的特徵點 對。保留有兩個特徵點對(7和11 ),而房間通常只有一個門。
圖6A和圖6B是圖3的部分A的放大示圖，圖6A和圖6B顯示了通過 比較將連接候選特徵點的線和網格地圖30連接到房間的邊界形成的閉合曲 線的長度，從候選特徵點對中提取最終特徵點對的過程。
可通過將特徵點對7的線和附圖中由粗線21繪製的網格地圖30連接來 形成閉合曲線。可通過將特徵點對7的線和沿箭頭方向在特徵點對7附近繪 制的網格地圖30連接來形成閉合曲線。在這種情況下，選擇兩個閉合曲線的 較小區域以便確定是否滿足最終特徵點對的要求。如果考慮圖6A的粗線21 形成的閉合曲線，則與正常房間的邊界相比，閉合曲線的邊界太小。因此， 特徵點對7被排除在最終特徵點對之外。
如上所述，通過連接特徵點對11和網4各地圖30可形成兩條閉合曲線。 如圖6B所示，由粗線25形成的較小閉合曲線的邊界與正常房間的邊界相似。 因此，滿足上述操作的要求的特徵點對11將變為最終特徵點對。
在提取最終特徵點對之後，通過連接該對產生臨界線(S230)。作為產生 整個區域的示例，在圖8A中臨界線由虛線繪製，將參照附圖對其進行詳細 描述。
從由產生的臨界線和網格地圖30形成的區域中刪除一些臨界線以形成 最終區域(S240)。
圖7是根據示例性實施例的形成區域的圖2的操作S240的詳細流程圖。 首先，當通過連接臨界線和網格地圖30形成的區域包括通過連接其他臨 界線和網格地圖形成的區域時，如果區域之間的面積差超過預定範圍，則從 較大的區域中分離較小的區域(S242)。優選地，預定範圍被設置為最小房間 的面積的一半，大約低於3.3m2。這是因為，如果區域之間的面積差大於該範 圍，則通過從較大的區域減去較小的區域形成的區域可包括這樣的區域，如 房間和客廳。
此外，當通過連接臨界線和網格地圖30形成的區域包括通過連接其他臨
界線和網格地圖形成的區域時，如果區域之間的面積差在預定範圍之內，則 刪除形成較小區域的臨界線以選擇較大的區域(S244)。這是因為，如果區域 之間的面積差小於該範圍，則通過從較大的區域減去較小的區域形成的區域
太小而難以識別。通常，優選地，預定範圍淨皮i殳置為最小房間的面積的一半。 參照圖8A、圖8B和圖8C，將舉例描述通過臨界線形成可識別區域的過程。
圖8A、圖8B和圖8C是顯示通過產生的臨界線來形成最終區域的過程 的示圖。
在圖8A中示出了從最終特徵點對產生的臨界線(11、 12、 13、 14、 15 和16)。在下文中，臨界線(ll、 12、 13、 14、 15和16)將由自己的標號表 示，如臨界線11、臨界線12。
當考慮臨界線11時，在圖8A中，兩個箭頭存在於臨界線11的右側和 左側。當臨界線11沿兩個箭頭(所述兩個箭頭位於臨界線的右側)方向連接 到網格地圖30時形成區域。此外，當臨界線11沿兩個箭頭(所述兩個箭頭 位於臨界線的左側)方向連接到網格地圖30時也形成區域。在這種情況下， 臨界線將一個區域劃分為兩個區域，並且選"^奪兩個區域中較小的區域以形成 區域。因此，通過臨界線11形成圖8B的暗區域。相同地，通過臨界線(12、 13、 14、 15和16)形成各個區域。
即使通過臨界線形成區域，這些區域也不是最終區域。這是因為， 一些 區域彼此重疊，而重疊的區域應該被處理。例如，當考慮通過臨界線13和臨 界線14形成的區域時，在由各個臨界線形成的兩個區域之間形成了重疊的區 域。即，由臨界線14形成的區域包括由臨界線13形成的區域。在這種情況 下，因為兩個區域之間的差遠小於最小房間的面積的一半，所以臨界線13被 刪除，並且較大的區域被選擇。另外在臨界線15和臨界線16的情況下，由 臨界線15形成的區域糹皮選糹,，而臨界線16被刪除。
在經歷刪除一些臨界線的操作之後，臨界線(ll、 12、 14和15)最終保 留，並且所述臨界線顯示在圖8C中。圖8C是顯示在經歷刪除一些臨界線的 過程之後最終保留的臨界線的示圖。通過使用臨界線和網格地圖30，整個區 域被劃分為五個最終區域。
圖9是顯示根據示例性實施例的產生的拓樸地圖的示圖。
為了不同的識別，經歷上述操作劃分的區域的閉合曲線具有彼此不同的圖(S250)。
在繪製拓樸地圖之後，劃分的區域可具有名稱，如房間1、房間2和客廳。
拓樸地圖可顯示在獨立的顯示裝置上(S260)。在機器人清潔器的情況下， 如果用戶選擇任意區域(房間1、客廳等)進行打掃，則機器人清潔器可識 別選擇的區域並進行打掃。
圖IO是根據示例性實施例的通過使用特徵點40劃分區域的設備的框圖。 根據示例性實施例的通過使用特徵點40劃分區域的設備包括網格地圖 生成單元310、特徵點提取單元320、候選特徵點對提取單元330、最終特徵 點對提取單元340、臨界線形成單元350和區域形成單元360，以便將整個區 域劃分為可識別區域。
劃分區域的設備還可包括拓樸地圖繪製單元370和顯示單元380。 網格地圖生成單元310使用通過檢測距障礙物的距離獲得的多個網格點 繪製網格地圖30。此時，可通過使用紅外線、雷射或超聲波來檢測距障礙物 的距離，但是使用的方法不限於此，並且可通過使用各種方法來檢測距障礙 物的距離。
特徵點提取單元320從由網格地圖生成單元310形成的網格地圖30中提 取特徵點40。可通過^f吏用RANSAC算法或SLAM (同時定位與地圖創建) 算法提取特徵點40以形成特徵點地圖，並且提取特徵點40的算法不限於此。
候選特徵點對提取單元330從特徵點提取單元320提取的特徵點40中提 取在區域劃分元素的範圍中的特徵點對。當提取候選特徵點對時，區域劃分 元素的範圍基於諸如入口門的寬度的通路來設置。優選地，在考慮由於網格 點的間隔而添加到通路的寬度的噪聲而設置的範圍內提取特徵點對。
最終特徵點對提取單元340從候選特徵點對提取單元330提取的候選特 徵點對中提取滿足區域劃分元素的要求的特徵點。此時，如果特徵點對的線 與網格地圖30重疊，則重疊的對被排除以從候選特徵點對中提取最終特徵點 對。此外，如果網格地圖30沒有包括特徵點對40,則特徵點對40被排除以 從候選特徵點對中提取最終特徵點對。如果通過連接特徵點對的線和網格地 圖30形成的閉合曲線的長度在預定範圍之內，則該特徵點對從候選特徵點對 中被提取，以變為最終特徵點對。此時，所述預定範圍基於房間的邊界來設 置。
臨界線形成單元350通過連接從最終特徵點對提取單元提取的特徵點對
形成臨界線。
區域形成單元360刪除一些在通過連接臨界線形成單元350生成的臨界 線和網格地圖30的閉合曲線形成的區域之間的臨界線，並產生最終區域。此 時，當通過連接臨界線和網格地圖30形成的區域包括通過連接其他臨界線和 網格地圖30形成的區域時，可從較大的區域中分離較小的區域。如果區域之 間的面積差在預定範圍之內，則形成較小區域的臨界線被刪除，以選擇較大 的區域。優選地，所述預定範圍設置為最小房間的面積的一半。
拓樸地圖繪製單元370基於區域形成單元360形成的最終區域繪製拓樸 地圖。
顯示單元380在顯示裝置上顯示拓樸地圖。此時，可通過例如使各個區 域具有不同的顏色來識別各個區域，並且用戶可選擇^&此劃分的區域。
當上述裝置安裝在機器人清潔器中並且用戶在顯示裝置上可識別地顯示 的拓樸地圖區域中選4奪預定區域時，^/L器人識別所選的區域以自動地打掃該 區域。
除了上述示例性實施例，本發明的示例性實施例也可通過"t丸行介質(如 計算機可讀介質)中/上的計算機可讀代碼/指令來實現。所述介質可對應於允 許存儲和/或傳輸計算機可讀代碼/指令的任何介質。所述介質還可包括單獨的 計算機可讀代碼/指令、數據文件和數據結構等，或者其組合。代碼/指令的示 例包括如通過編譯器產生的機器代碼和包含可使用解釋器通過計算裝置等執 行的高級代碼的文件。此外，代碼/指令可包括功能程序和代碼段。
計算機可讀代碼/指令可以以各種方式在介質中/上記錄/傳送，所述介質
的例子包括可包括計算機可讀代碼/指令、數據文件、數據結構等的磁存儲介 質(例如，軟盤、硬碟、磁帶等)、光學介質(例如，CD-ROM、 DVD等)、 磁光介質(例如，光軟盤)、硬體存儲裝置(例如，只讀存儲介質、隨機存取 存儲介質、快閃記憶體等)和諸如傳輸信號的載波的存儲/傳輸介質。存儲/傳輸介質 的例子可包括有線和/或無線傳輸介質。所述介質還可以是分布式網絡，從而 計算機可讀代碼/指令可以以分布式方式被存儲/傳送和執行。計算機可讀代碼 /指令可以由一個或多個處理器執行。計算機可讀代碼/指令還可以在至少一個
專用集成電路(ASIC)或現場可編程門陣列(FPGA)中執行，或嵌入其中。 此外，可構造一個或多個軟體模塊或者一個或多個硬體模塊以便執行上
述示例性實施例的操作。
這裡所使用的術語"模塊"表示，但不限於，執行特定任務的一個軟體 組件、 一個硬體組件，多個軟體組件、多個硬體組件、 一個軟體組件和一個 硬體組件的組合、多個軟體組件和一個硬體組件的組合、 一個軟體組件和多 個硬體組件的組合或者多個軟體組件和多個硬體組件的組合。模塊可被方便 地構造為駐留在可尋址存儲介質上，並可被構造為在一個或多個處理器上運 行。因此，作為示例，模塊可包括諸如軟體組件、專用軟體組件、面向對象 的軟體組件、類組件和任務組件的組件、進程、函數、操作、執行線程、屬 性、過程、子程序、程序代碼段、驅動程序、固件、微碼、電路、數據、數 據庫、數據結構、表、數組和變量。所述組件或模塊中提供的功能可被組合 為更少的組件或模塊，或者可被進一步分為另外的組件或模塊。此外，所述 組件或模塊可在裝置中設置的至少一個處理器(例如，中央處理單元(CPU ))
上運行。此外，硬體組件的例子包括專用集成電路(ASIC)和現場可編程門 陣列(FPGA)。如上所述，模塊還可表示軟體組件和硬體組件的組合。這些 硬體組件還可以是一個或多個處理器。
計算機可讀代碼/指令和計算機可讀介質可以是為本發明的目的而專門 設計和構建的，或者可以是計算機硬體和/或計算機軟體領域的技術人員公知 的可用類型。
通過使用上述特徵點來劃分區域的方法、設備和介質的示例性實施例不 限於機器人清潔器，這些示例性實施例可應用於安全機器人、嚮導機器人、 服務機器人、任意移動機器人等。
上述示例性實施例具有如下的一個或多個有益效果。
第一、當網格地圖被劃分為可識別區域，如房間、客廳等時，用戶可以 以便利的方式指定區域。
第二，可通過使用從網格地圖提取的特徵點提取臨界線，以便使用較少 的計算量來簡單地劃分區域。
第三，當繪製的拓樸地圖被顯示在機器人清潔器的顯示裝置上，並且用 戶選擇劃分的預定區域時，機器人清潔器可打掃該區域。
雖然已經顯示和描述了 一些示例性實施例，但是本領域:技術人員應該理 解，在不脫離本發明的原則和精神的情況下，可以對這些示例性實施例進行 改變，本發明的範圍由權利要求及其等同物限定。
權利要求
1、一種通過使用特徵點劃分區域的方法，所述方法包括通過使用多個網格點形成網格地圖，其中，通過檢測與障礙物之間的距離獲得所述網格點；從網格地圖提取特徵點；從特徵點提取包括在區域劃分元素的範圍中的候選特徵點對；從候選特徵點對提取滿足區域劃分元素的要求的最終特徵點對；通過將最終特徵點對彼此連接來形成臨界線；和根據具有通過連接臨界線和網格地圖形成的閉合曲線的區域之間的大小關係形成最終區域。
2、 如權利要求l所述的方法，其中，在形成網格地圖的步驟中，通過使 用紅外線傳感器、雷射傳感器或超聲波傳感器中的任意一種來檢測與障礙物 之間的距離。
3、 如權利要求l所述的方法，其中，提取特徵點的步驟包括通過使用 隨機採樣一致性算法來提取特徵點。
4、 如權利要求l所述的方法，其中，提取特徵點的步驟包括通過使用 同時定位與地圖創建算法來提取特徵點。
5、 如權利要求l所述的方法，其中，在提取候選特徵點對的步驟中，基 於通路的寬度設置區域劃分元素的距離範圍。
6、 如權利要求5所述的方法，其中，從特徵點提取候選特徵點對的步驟 包括提取候選特徵點對，所述候選特徵點對包括在考慮由於通路的寬度的範 圍內的網格點之間的間隔造成的噪聲設置的距離範圍之內。
7、 如權利要求l所述的方法，其中，提取最終特徵點對的步驟包括提 取除了與網格地圖重疊的連接特徵點對的線之外的最終特徵點對。
8、 如權利要求7所述的方法，其中，提取最終特徵點對的步驟還包括 提取除了不包括在網格地圖中的特徵點對之外的最終特徵點對。
9、 如權利要求l所述的方法，其中，提取最終特徵點對的步驟還包括提 取這樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲線 的長度在預定長度範圍之內。
10、 如權利要求9所述的方法，其中，基於房間的邊界設置預定長度範 圍。
11、 如權利要求1所述的方法，其中，形成最終區域的步驟包括當閉合曲線形成的區域彼此包括，並且所述區域的面積差超出預定範圍時，從較 大的區域分離較小的區域。
12、 如權利要求l所述的方法，其中，形成最終區域的步驟包括當閉 合曲線形成的區域彼此包括，並且所述區域的面積差在預定範圍之內時，刪 除形成較小區域的臨界線。
13、 如權利要求11所述的方法，其中，基於最小房間的面積的一半設置 預定範圍。
14、 如權利要求12所述的方法，其中，基於最小房間的面積的一半設置 預定範圍。
15、 如權利要求1所述的方法，還包括基於在形成最終區域的步驟中 形成的最終區域繪製拓樸地圖。
16、 如權利要求15所述的方法，還包括在顯示裝置上顯示拓樸地圖。
17、 一種通過使用特徵點劃分區域的設備，所述設備包括 網格地圖生成單元，通過使用多個網格點形成網格地圖，其中，通過檢測與障礙物之間的距離獲得所述網格點；特徵點提取單元，從網格地圖提取特徵點；候選特徵點對提取單元，從特徵點提取包括在區域劃分元素的範圍之內 的特徵點對；最終特徵點對提取單元，從候選特徵點對提取滿足區域劃分元素的要求的最終特徵點對；臨界線形成單元，通過連接最終特徵點對來形成臨界線；和區域形成單元，根據連接臨界線和網格地圖的閉合曲線形成的區域之間的大小關係形成最終區域。
18、 如權利要求17所述的設備，其中，通過使用紅外線傳感器、雷射傳 感器或超聲波傳感器中的任意一種來檢測與障礙物之間的距離。
19、 如權利要求17所述的設備，其中，通過使用隨機釆樣一致性算法來 提取特徵點。
20、 如權利要求17所述的設備，其中，通過使用同時定位與地圖創建算 法來提取特徵點。
21、 如權利要求17所述的設備，其中，當候選特徵點對提取單元提取候選特徵點對時，基於通路的寬度設置區域劃分元素的範圍。
22、 如權利要求21所述的設備，其中，候選特徵點對提取單元提取候選 特徵點對，所述候選特徵點包括在考慮由於通路的寬度的範圍內的網格點之 間的間隔產生的噪聲設置的距離範圍之內。
23、 如權利要求17所述的設備，其中，最終特徵點對提取單元提取除了 與網格地圖重疊的連接特徵點對的線之外的最終特徵點對。
24、 如權利要求23所述的設備，其中，最終特徵點對提取單元提取除了 不包括在網格地圖中的特徵點對之外的最終特徵點對。
25、 如權利要求17所述的設備，其中，最終特徵點對提取單元還提取這 樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲線的長 度在預定長度範圍之內。
26、 如權利要求25所述的設備，其中，基於房間的邊界設置預定長度範圍。
27、 如權利要求17所述的設備，其中，當閉合曲線形成的區域彼此包括， 並且所述區域的面積差超出預定範圍時，區域形成單元從較大區域分離較小 區域。
28、 如權利要求17所述的設備，其中，當閉合曲線形成的區域彼此包括， 並且所述區域的面積差在預定範圍之內時，形成最終區域的步驟刪除形成較 小區域的臨界線。
29、 如權利要求27所述的設備，其中，基於最小房間的面積的一半設置 預定範圍。
30、 如權利要求28所述的設備，其中，基於最小房間的面積的一半設置 預定範圍。
31、 如權利要求17所述的設備，還包括拓樸地圖形成單元，基於最終 區域繪製拓樸地圖。
32、 如權利要求31所述的設備，還包括顯示裝置，在顯示裝置上顯示 拓樸地圖。
33、 一種具有通過使用特徵點劃分區域的設備的機器人，所述設備包括 網格地圖生成單元，通過使用多個網格點形成網格地圖，其中，通過檢測與障礙物之間的距離獲得所述網格點；特徵點提取單元，從網格地圖提取特徵點；候選特徵點對提取單元，從特徵點提取包括在區域劃分元素的範圍之內的特徵點對；最終特徵點對提取單元，從候選特徵點對提取滿足區域劃分元素的要求 的最終特徵點對；臨界線形成單元，通過連接最終特徵點對來形成臨界線；和區域形成單元，根據連接臨界線和網格地圖的閉合曲線形成的區域之間 的大小關係形成最終區域；拓樸地圖形成單元，基於最終區域形成拓樸地圖；和顯示單元，在顯示裝置上顯示拓樸地圖，其中，當選擇在顯示裝置上可識別地顯示的拓樸地圖的預定區域時，自 動打掃所述區域。
34、 如權利要求7所述的方法，其中，提取最終特定點對的步驟還包括 提取這樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲 線的長度在預定長度範圍之內。
35、 如權利要求34所述的方法，其中，基於房間的邊界設置預定長度範圍。
36、 如權利要求8所述的方法，其中，提取最終特定點對的步驟還包括 提取這樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲 線的長度在預定長度範圍之內。
37、 如權利要求36所述的方法，其中，基於房間的邊界設置預定長度範圍。
38、 如權利要求11所述的方法，其中，形成最終區域的步驟還包括當 閉合曲線形成的區域彼此包括，並且所述區域的面積差在預定範圍之內時， 刪除形成較小的區域的臨界線。
39、 如權利要求38所述的方法，其中，基於最小房間的面積的一半設置 預定範圍。
40、 如權利要求23所述的設備，其中，最終特徵點對提取單元還提取這 樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲線的長度在預定長度範圍之內。
41、 如權利要求40所述的設備，其中，基於房間的邊界設置預定長度範 圍。
42、 如權利要求24所述的設備，其中，最終特徵點對提取單元還提取這 樣的最終特徵點對通過連接特徵點對的線和網格地圖形成的閉合曲線的長 度在預定長度範圍之內。
43、 如權利要求42所述的設備，其中，基於房間的邊界設置預定長度範圍。
44、 如權利要求17所述的設備，當閉合曲線形成的區域彼此包括，並且 所述區域之間的面積差在預定範圍之內時，形成最終區域的步驟刪除形成較 小區域的臨近線。
45、 如權利要求44所述的設備，其中，基於最小房間的面積的一半設置 預定範圍。
46、 如權利要求17所述的設備，其中，所述設備是移動機器人的一部分。
47、 如權利要求46所述的設備，其中，所述移動機器人是清潔機器人。
48、 如權利要求33所述的設備，其中，所述移動機器人是清潔機器人。
49、 至少一種計算機可讀介質，所述計算機可讀介質存儲控制至少一個 處理器以實現權利要求1所述的方法的計算機可讀指令。
全文摘要
提供一種通過使用特徵點劃分區域的設備、方法和介質。所述方法包括通過使用多個網格點形成網格地圖，通過檢測與障礙物之間的距離獲得所述網格點；從網格地圖提取特徵點；從特徵點提取區域劃分元素的範圍中的候選特徵點對；從候選特徵點對提取滿足區域劃分元素的要求的最終特徵點對；通過連接最終特徵點形成臨界線；和根據具有通過連接臨界線和網格地圖形成的閉合曲線的區域之間的大小關係形成最終區域。
文檔編號G05D1/02GK101101203SQ20071012823
公開日2008年1月9日 申請日期2007年7月5日 優先權日2006年7月5日
發明者方錫元, 鉉 明, 李受珍, 李榮範 申請人:三星電子株式會社