TW201609432A - 用於資料分割操作有效性判定之方法及裝置 - Google Patents

Abstract

本發明的實施例提供判定資料是否超過一操作之一有效範圍的一種方法，其包含有把指出該操作之一有效範圍的操作資料分割成數個資料塊；為該等數個資料塊的每一個判定一部分凸包；基於該等數個部分凸包判定用於該操作資料的一凸包；以及基於該凸包判定該資料是否超過該操作資料的該有效範圍。

Description

用於資料分割操作有效性判定之方法及裝置

本發明係有關於用於資料分割操作有效性判定之方法及裝置。

發明背景

在成像領域中，諸如影像校正、印刷等等，它通常需要把解決方案，如校正技術、彩色模式、彩色映射演算法等等，套用到輸入資料。然而，如此的解決方案有一它們已知可工作的有效範圍。該有效範圍通常是，雖然不是唯一地，衍生自從其該解決方案被導出之測量資料。舉例來說一種校正方法可從一反射範圍被衍生出，一種顏色映射演算法可基於一墨水向量範圍，以及一種顏色配置文件可基於一測量範圍。一種解決方案所基礎之該資料將在下文中被稱為操作資料。

如果一種解決方案被套用到該解決方案所基礎之該操作資料之外的影像資料，那麼在輸出資料中可能會有偽影或可能會發生該解決方案的失效。

本發明實施例的一目的係至少緩和該等現有技 術問題的一個或多個。

依據本發明之一實施例，係特地提出一種判定資料是否超過一操作之一有效範圍的方法，其包含有：把指出該操作之一有效範圍的操作資料分割成數個資料塊；為該等數個資料塊的每一個判定一部分凸包；基於該等數個部分凸包判定用於該操作資料的一凸包；以及基於該凸包判定該資料是否超過該操作資料的該有效範圍。

300‧‧‧方法

310‧‧‧降低維度

320‧‧‧隨機化資料

330‧‧‧分割資料

340‧‧‧判定部分凸包

350‧‧‧判定凸包

360‧‧‧映射

400‧‧‧系統

410‧‧‧處理單元

420‧‧‧記憶體

430‧‧‧I/O單元

440‧‧‧列印單元

本發明的實施例現在將僅以示例的方式來描述，參照該等附圖，其中：圖1展示出計算時間的一例示，用於計算各種資料的一凸包；圖2展示出計算時間的另一例示，用於計算各種資料的一凸包；圖3根據本發明的一實施例展示出一種方法；圖4根據本發明的一實施例展示出一種系統；圖5圖示出具有不同維度數之反射資料的覆蓋率；以及圖6根據本發明的一實施例圖示出一種方法的效能。

較佳實施例之詳細說明

本發明的實施例提供用於有效性檢查的方法及裝置。有效性檢查包括判定輸入資料，當在其上它被意圖要執行一種操作時，是否落在該操作所基於之操作資料的 一種領域或範圍或已知是有效的一種領域或範圍之外。舉例來說，判定該輸入資料是否落在一演算法所基於之資料之外。該操作可以是一種校正方法、一種顏色模型、一種參考系統效能等等。如果該輸入資料落到該操作資料的該領域或範圍之外，則可以產生一警告，該操作停止；或另一種替代的，有時是具較低準確性的，對外插更為穩健的操作可被執行。

一種凸包或凸包絡可被使用來判定一組資料諸如操作資料的一邊界或範圍，即該資料的極端頂點。對於具有大維度數的資料，諸如N>5，其中N係該資料集的維度數，一凸包的計算會是困難的。大部分的凸包計算方法旨在使用於具有兩維或三維的資料。然而，反射資料通常係16維或31維，或更高維度的；墨水向量可具有4至12之間的維度；以及用於列印的3D物件描述也可具有附加的維度，諸如材料屬性和色度，導致總共有4(3D座標+材料)、7(+XYZ色度)或更多的維度。將被理解的是，這些維度數僅是例示性的。類似地，計算大量資料點的一凸包，或大量資料點並具大維度數的一凸包，可以是同樣困難的，如將可被理解的。

圖1展示出使用由福田公明所提出之一種雙描述方法(cdd)為包括各種數量之樣本和維度的資料集計算一凸包的時間。正如可被理解的那樣，增加該資料樣本和維度數量顯著地增加了該計算時間。對於一相對較小的資料集(在這種情況下，3000個樣本)這方法直到16維或許更多維是 有用的。然而，對於非全秩的資料，其係非全維度或係叢聚的，或用於大量的樣本中，該方法會顯著地變慢。因此，使用cdd凸包判定的速度取決於以下的一個或多個：該資料的真實維度(均勻隨機點計算的速度會比，舉例來說，反射資料要快)；該資料的該名目維度；以及樣本點的該數量。

圖2展示出使用在MATLAB中所提供的一種稱為convhulln程序(其又是基於一開放原始碼qhull庫)來為包含有不同數目的樣本和維度的資料集計算一凸包的時間。應被指出的是，不同於圖1，該時間軸係對數型態的。雖然這種技術在六維中比較快，但可留意到在高於八維時會迅速地變慢。因此，本發明的實施例旨在增進使用具較大維度數，特別是N>6，和/或具較大量資料點之資料時的可使用性。

圖3根據本發明的一實施例圖示出一種方法300。該方法300係一種用於判定操作資料之一凸包的方法以致能輸入資料的有效性檢查。

在圖3所示的該方法將參照描繪在圖4中的一種系統400。該系統400包括一處理單元410用於執行形成電腦軟體的指令，用於實現根據本發明一實施例的一種方法。該處理單元410可包括數個處理器和/或處理核心，每一個都能夠獨立地執行指令。該處理單元410可以包括一個或多個CPU、GPU、FPGA或類似物。該軟體可被儲存在該系統的一記憶體420中，其可以包括一唯讀部分以儲存該等電腦可執行指令。該記憶體420還可以包括一可重寫入部分，用 於在該系統400的操作過程中儲存資料。該記憶體420可儲存輸入資料，其根據本發明的一實施例被需要來判定一操作的該有效性。該記憶體420可以替代地或額外地儲存該操作所基於的該資料，諸如該操作資料，其中一凸包將被判定。該操作所基於的該資料將在下文中被稱為操作資料。將被理解的是，該記憶體420可以只儲存該操作所基於之該資料的一代表性部分，使用該代表的操作資料該操作的該有效性可被檢查。該系統400還可以包括，在一些實施例中，一I/O單元430和/或一440列印單元440。該I/O單元440可以包括以下的一個或多個：一用於與其他的裝置通信資料的裝置，諸如經由一種網路，該網路可以是一種有線或無線連接；一用於接收一使用者輸入的裝置，諸如透過一個或多個按鍵或按鈕；以及一輸出裝置用於輸出資訊給一使用者，諸如以一種顯示器裝置的形式。在一些實施例中，用於接收該使用者輸入的裝置和該輸出裝置可被合併，舉例來說，以一種觸控敏感之顯示器裝置的形式。該列印單元440係用於列印出對應於被儲存在該記憶體420中之影像資料的一影像。該影像資料可基於需要有以檢查該操作有效性的該輸入資料。

回到圖3，該方法300包括降低該操作資料維度的一步驟310。步驟310可以包括子步驟來判定該操作資料的一較低維度數並在該判定之較低維度數的基礎上把該操作資料映射到一模型。

該操作資料可具有由N×N _smp 所定義的一維度 數。該步驟310輸出係具有維度N×N _D 的資料，其中N _D <N _smp 。該操作資料可被儲存在該系統400的該記憶體420中而由步驟310的該資料輸出也可被儲存在該記憶體420中。

步驟310可以包括在該操作資料上執行線性或非線性的維度數降低。該線性維度數降低可包括在該操作資料執行主成分分析(PCA)，以判定該操作資料的一種「真正的」維度數。換句話說，在步驟310的該第一子步驟中，係判定該操作資料的一維度數是否可以被降低。該PCA判定該降低維度數N _D 的值，使得高於一預定的變異被表現在該資料中，其中該預定變異可以是高於90%、95%、基本上100%或正好為100%。如果N _D 小於N _smp 則步驟310的該第二子步驟被執行，或如果N _D 等於N _smp 則該方法移動到步驟320。

步驟310的該第二子步驟包括在N _smp 空間中執行該N×N _smp 操作資料的一線性映射，映射到該較低維度的N _D 空間。這減少了該操作資料由N×N _smp 到N×N _D ，其中N _D 小於N _smp ，從而降低了該操作資料的該維度數。

該第二子步驟可以被稱為線性子空間投影。在此子步驟中，在N _smp 維中數個資料點被映射到在一N _D 維子空間中最近的點，該子空間係由在這空間中一組N _smp 向量所定義的(一N _D ×N _smp 矩陣B，其中該矩陣的該等N _D 列係定義該N _smp 維子空間之該等軸的該等向量，因此係該等N _smp -向量的N _D )。其中這些產生自PCA的該等向量也正交。如果我們把這組向量表示為B，則該投影矩陣被定義為P=B*B^T*B(其 中B^T係該轉置)。由於B係正交的，B^T*B係該單位矩陣，因此P=B並且如果S係在一N×N _smp 矩陣中所表示之在N _smp 維中該N點資料集，則其在該降低維度領域N _D 中的表示為Q=S^T*B使得Q係N×N _D 。

圖5展示出具有不同維度數之資料的譜反射覆蓋。以%所表示之該覆蓋率的決定係採用主成分分析(PCA)和多光源參數△E(MIPE)色差(DE00)。該反射資料包括54,000個樣本。從圖5中可以看出較低維度的資料可以良好地表示具較高維度的資料，直到一較低的截止點。

應被指出的是，在一較低維度中的操作並不意味著較低的精準度。較低維度資料的極端頂點也可能是較高維度極端頂點的一子集，雖然一凸包體積的一部分可能會因在維度的該降低而被犧牲掉。

在可選擇的步驟320中，該操作資料被重新排序，以減少該資料的任何結構。將被體認的是，步驟320可以執行在步驟310之前，或如在圖3中所示之後。在步驟320中，該資料集被重新排序以提高資料的一種隨機性。如果該資料集有一固有的順序，這對該方法稍後的步驟可能是不利的。

在可選擇的步驟330中，判定該資料是否具有大於一預定的樣本數。如果該資料具有大於一預定數量K的樣本，其中K可以是3000、5000或可被選擇的其他樣本數，該資料會被分割成資料塊。每一資料塊可以是同樣大小的並且可以包括一預定數量的樣本。該等預定的樣本數量係一 種樣本數量其可由該處理單元410的每一個處理器或核心來處理。該樣本數量也可以根據處理器或CPU或GPU核心之可平行計算的可用數量來決定。每一資料塊包括K個樣本，儘管將會被體認的是，其他的數量可被選擇。

在步驟340中，為在步驟330中所決定之該等資料塊的每一個判定一部分凸包。每一個部分凸包的判定被分配給一各別的核心或處理器，在下文中一般被稱為該處理單元410的一處理單元。每一個部分凸包的該判定因此可由該等各別處理單元至少部分地被平行執行以減少步驟340的處理時間。

每一個各別的處理單元可判定該部分凸包(每一個各別資料塊的一凸包)，使用如以上所提及之一程序諸如cdd、qhull或convhulln。將也被理解的是，其他的方法也可被使用。此外，將被理解的是，每一個處理單元可為數個資料塊判定一部分凸包，即該資料塊數可以多於該處理單元數，並且每一個處理單元可能不是分配相同數量的資料塊。步驟340由此判定數個部分凸包的極端頂點。對於每一第i個資料塊K _i ×N _smp 該凸包計算傳回一組新的極端頂點P _i ×N _smp 其中P _i <=K _i (等號成立於若且唯若該資料塊所有的點都已經在該凸包上)。該等極端頂點然後可被結合成一單一L×N _D 資料集，其中L係在該等K _i ×N _D 資料集上該等部分凸包計算的該總和使得L=P₁+P₂+P₃...並使得L<=N(該極端頂點總和小於或等於所有的初始資料點，等於的情況成立在若且唯若所有的初始點都始於在該凸包上)。

如果該樣本數L大於一預定的臨界值，步驟330和340可被重複。該重複進一步分割該等資料點成為資料塊，並為那些資料塊計算部分凸包。此外，如果在分割成資料塊以及隨後的部分凸包計算之後L近似於N，則該原始資料集已經很大程度地已在該凸包上，故進一步的重複是沒有用的。因此，該方法300可包括一決定步驟，在其中判定是否要重複步驟330-340一次或多次。

在步驟350，由步驟340所產生之該等部分凸包的該等頂點的一總凸包被判定。即，在步驟350中，來自步驟340之聯合凸包的一凸包被判定。其結果是在一種線性模型基礎中的一組M×N _D 點，其中M係嚴格地在該聯合資料集之該凸包上該頂點數，該聯合資料集係來自於在該等K _i ×N _D 資料塊上該等部分凸包計算，而且M<=L(該整體凸包最多和該等部分凸包之該總和有一樣多的頂點)。

在步驟360中，具有N _D 維度的該等點被投影或映射回N _smp 維度以用M×N _smp 的形式傳回資料。

在一進一步的步驟中，未在圖3中示出，其可在步驟360之後被執行，輸入資料可對M×N _smp 的凸包進行比較以判定該輸入資料是否落在該操作資料的該凸包之外。這可以以多種方式來實現，例如把該凸包重新表現為一組半空間(線性不等式)，其可透過把一新資料點對所有的線性不等式進行評估的方式來做快速的包含檢查，如果該資料點滿足所有的不等式(其定義該凸包)，這意味著它在該凸包內，否則是在其之外。其他的方法，諸如一基於行列式的 方法等等，對本領域的習知技藝者來說係熟知的。

如果該輸入資料，至少部分地，落在該凸包之外，則可輸出一警告，指出將在該輸入資料上執行之一種操作的有效性不被保證。在另一實施例中，如果該輸入資料落在該凸包之外的話，該操作可被停止，或僅計算滿足該凸包之該輸入資料部分(即落在該凸包內)的部分結果。可替代地，在落在該凸包之外的該輸入資料可執行一種不同的方法或操作。在這種情況下，一警告可被提供，例如有關於使用方法的一種異質性警告。

圖6展示出cdd對上根據本發明之一實施例為具有各種維度資料判定一凸包之方法的比較。正如可從圖5中體認的是，對於反射資料，根據本發明之一實施例的該方法顯著地優於該cdd方法。

雖然該等上述實施例已經參照反射資料被描述，將被理解的是，本發明的實施例並不一定侷限於這樣的資料來使用。本發明的實施例可以與以下的任一來使用：通常是高維度的(常見的格式為16、31或101取樣維度)反射資料，通常可由PCA被良好的表示。

色度資料(CIE XYZ、LAB、等等)，其雖然不高維度但可能包含大量的樣本。

墨水向量，其維度數直接取決於墨水數，例如4至12，儘管可預知可能會有更多維度。

HANS NPacs把列印描述為「Neugebauer Primary區域覆蓋」，其實際上向量並非在墨水空間中，而是在 Neugebauer Primary空間中，其係所有墨水套印的區域。例如，對於一個4-墨水二進制(有墨水、無墨水)列印系統來說，存在有2⁴=16維度，其中如果有兩種液滴尺寸(無墨、1滴、2滴)，存在有3⁴=81維度。正如可被理解的是，可能會有大量的維度。在一其他的實例中，一以RGB索引的顏色查詢表可以包括(例如，17³=4913個樣本)在一81維度區域中。

3D列印資料可能超出3個維度(x、y、z座標)特別是當在每一個空間位置上涉及其他的屬性時，諸如材料或顏色。因此該資料包含4(3座標+1材料)、7(3座標、1材料、3顏色)或更多維度以及還涉及非常大的資料點(10K+)集合。

正如可被理解的，本發明的實施例提供用於判定一操作之有效性的方法和裝置。這些方法和裝置包括基於數個部分凸包來判定一凸包。

將被理解的是，本發明的實施例可以以硬體、軟體或硬體和軟體組合的形式來實現。任何這樣的軟體可以被儲存在依電性或非依電性儲存的形式，諸如，舉例來說，像一ROM的一種儲存裝置，不管是可擦除式或可重寫與否，或者以記憶體的形式，諸如，舉例來說，RAM、記憶體晶片、裝置或積體電路或在一光學或磁性可讀取媒體上，諸如，舉例來說，一CD、DVD、磁盤或磁帶。將被理解的是，該等儲存裝置和儲存媒體係機器可讀取儲存的實施例，其適合於儲存一個或多個程式，當執行時，實現了 本發明的實施例。因此，實施例提供了一程式，其包括用於實現如前述任一權利請求項所請求的一種系統或方法，以及一儲存如此一程式之機器可讀取儲存。更進一步地說，本發明的實施例可以經由任何媒體以電的方式來輸送，諸如在一有線或無線連接上所傳送的通信信號以及適當地包括該相同物的實施例。

所有在本說明書(包括任何所附的權利請要求項、摘要和附圖)所揭露的所有特徵、和/或任何方法或過程所揭露之所有的步驟，可以以任何組合的方式來結合，除非如此特徵和/或步驟的其中至少一些是相互互斥的。

在本說明書(包括任何所附的權利請要求項、摘要和附圖)所揭露的每一個特徵可被替換成具有相同、等效或類似目的替代特徵，除非另有明確地說明。因此，除非另有明確地說明，否則所揭露的每一個特徵僅是一般系列之等效或類似特徵的一個實例而已。

本發明並不侷限於任何前述實施例的細節。本發明延伸至在本說明書(包括任何所附的權利請要求項、摘要和附圖)所揭露的該等特徵之任何新穎的一個、或任何新穎的組合，和/或任何方法或過程所揭露之所有步驟之任何新穎的一個、或任何新穎的組合。該等權利要求項不應被解讀為僅覆蓋前述的實施例，應也覆蓋任何其落入該等權利要求項範疇之內的實施例。

300‧‧‧方法

310‧‧‧降低維度

320‧‧‧隨機化資料

330‧‧‧分割資料

340‧‧‧判定部分凸包

350‧‧‧判定凸包

360‧‧‧映射

Claims (15)

1. 一種判定資料是否超過一操作之一有效範圍的方法，其包含有：把指出該操作之一有效範圍的操作資料分割成數個資料塊；為該等數個資料塊的每一個判定一部分凸包；基於該等數個部分凸包判定用於該操作資料的一凸包；以及基於該凸包判定該資料是否超過該操作資料的該有效範圍。
2. 如請求項1之方法，其包含有判定該操作資料的一降低維度數。
3. 如請求項2之方法，其中該判定包含有在該操作資料上執行一主成分分析(PCA)。
4. 如請求項2之方法，其包含有把該操作資料映射到一基於該降低維度數的模型。
5. 如請求項4之方法，其中該模型係一種線性模型。
6. 如請求項1之方法，其包含有隨機化該操作資料。
7. 如請求項1之方法，其中該等部分凸包的至少一些係被平行地判定。
8. 如請求項1之方法，其中該判定該資料是否超過該操作資料之該有效範圍包含有把該凸包的頂點映射到該操作資料的一原始維度並把該資料與在該原始維度中的 該等頂點做比較。
9. 如請求項1之方法，其包含有輸出一種指示，其取決於該資料是否超過該操作資料之該有效範圍的該判定。
10. 一種裝置，其包含有：一記憶體；以及一處理單元，其中該處理單元被佈置來執行指令以執行一種方法，其包含有：把儲存在該記憶體中指出一操作之一有效範圍的操作資料分割成數個資料塊；為該等數個資料塊的每一個判定一部分凸包；基於該等數個部分凸包判定用於該操作資料的一凸包；以及基於該凸包判定該資料是否超過該操作資料的該有效範圍。
11. 如請求項10之裝置，其中該處理單元被佈置來判定該操作資料的一降低維度數。
12. 如請求項11之裝置，其中該處理單元被佈置來把該操作資料映射到一基於該降低維度數的模型。
13. 如請求項10之裝置，其中該處理單元被佈置來隨機化該操作資料。
14. 如請求項10之裝置，其包含有數個處理單元，其中每一個處理單元被佈置成至少部分平行地判定一個部分凸包。
15. 如請求項10之裝置，其中該裝置係一種影像處理裝置。