एक बड़े ज्ञात सेट

Question

के खिलाफ रंग पैटर्न मिलान के लिए एक एल्गोरिदम सुझाएं, मेरे पास एक आवश्यकता है जो किसी सटीक मिलान या स्वीकार्य दूरी के भीतर वाले मिलान खोजने के लिए मानों के ज्ञात सेट के विरुद्ध रंग मूल्यों के नमूना सेट से मेल खाने के लिए कॉल करती है । मुझे पूरी तरह से यकीन नहीं है कि इसके लिए एल्गोरिदम सबसे उपयुक्त होगा और मैं सुझावों की तलाश में हूं।

मैंने एक SQL क्वेरी का उपयोग करने के बारे में सोचा था क्योंकि मुझे लगता है कि यह एक सीधा दृष्टिकोण होगा, हालांकि, आदर्श रूप से यह एप्लिकेशन सर्वर पर या अधिकतम गति के लिए GPU पर भी स्मृति में किया जाएगा।

उदाहरण:

मान लीजिए कि हम तीन आरजीबी रंग मूल्यों, दो ब्लूज़ का एक सेट और एक नारंगी दिया जाता है:

नमूना सेट:

रंग 1: 81,177,206 (नीला)

रंग 2: 36, 70, 224 (नीला)

रंग 3: 255, 132, 0 (नारंगी)

3 रंग मानों का यह सेट रंग मानों के एक बड़े सेट के खिलाफ मिलान किया जाना चाहिए यह देखने के लिए कि यह सेट इसके भीतर मौजूद है या नहीं, या तो सटीक आरजीबी मानों के साथ 3 रंगों में से प्रत्येक - या - यदि कोई पैटर्न मौजूद है जहां रंगों का आरजीबी मान एक स्वीकार्य डिग्री से भिन्न होता है। आइए मान लें कि आरजीबी घटकों में से कोई भी 3 अंकों तक या मूल्य में कम हो सकता है।

के ज्ञात रंग मान है कि हम इस तरह दिखता है के खिलाफ खोज करेंगे के बारे में हमारी बड़ी सेट करते हैं:

ज्ञात सेट:

  Color 1   Color 2  Color 3 
Sample A: [25, 25, 25], [10, 10, 10], [100, 100, 100] 

Sample B: [125, 125, 125], [10, 10, 10], [200, 200, 200] 

Sample C: [13, 87, 255], [10, 10, 10], [100, 100, 100] 

Sample D: [67, 111, 0], [10, 10, 10], [200, 200, 200] 

Sample E: [255, 255, 255], [10, 10, 10], [100, 100, 100] 

इस परिदृश्य को देखते हुए, हम शून्य मिलान प्राप्त होता है जब हम इसके खिलाफ हमारे नमूना सेट को चलाएं, क्योंकि ज्ञात रंगों में से कोई भी रंग 1 नहीं है जो हमारे नमूना सेट मानों के करीब कहीं भी है। ,

Sample F: [81,177,206], [36, 70, 224], [255, 132, 0] 

नमूना एफ ज्ञात सेट में इन मूल्यों के साथ ही अस्तित्व में है, तो हम एक सकारात्मक हिट मिल जाएगा क्योंकि यह सटीक आरजीबी है: हालांकि, के नाम से जाना जाता सेट करने के लिए एक और रंग जोड़ने कि एक सकारात्मक मैच वापसी होगी जाने हमारे नमूना सेट में रंग 1 के रूप में मूल्य।इसके अलावा, हम आरजीबी मूल्यों में अंतर के अलग तरह का स्वीकार करने की जरूरत है, तो निम्न भी सकारात्मक हिट वापसी होगी क्योंकि प्रत्येक आरजीबी मूल्य नमूना सेट से रंग 1 के मूल्यों से 3 अंक के भीतर है:

सकारात्मक हिट: (याद रंग 1: 81,177,206)

नमूना एफ: , 177,206 (लाल चैनल 1 अंकों की दूरी पर है)

नमूना एफ: 81, , (हरे और नीले चैनलों 2 अंक दूर)

नमूना एफ: 82.179.208

(सभी तीन 3 अंक दूर भीतर चैनल) हालांकि, दूरी बहुत अधिक है, तो एक मैच नहीं मिला दिया जाएगा। सकारात्मक परिणाम ट्रिगर करने के लिए कोई भी आरजीबी घटक 3 अंकों के भीतर होना चाहिए।

नकारात्मक हिट:

नमूना एफ: , 177,206 (लाल चैनल है तो अगर नमूना एफ निम्नलिखित की तरह दिखाई देता है, हम नहीं एक सकारात्मक परिणाम दूरी बहुत अधिक है क्योंकि मिलेगा 4 अंक दूर)

नमूना एफ: 81, , 206 (हरा चैनल 7 अंक दूर)

नमूना एफ है: 81,177, (नीला चैनल 6 अंकों दूर है)

अब तक हमने नमूना सेट से रंग 1 को ध्यान में रखा है। हालांकि आवश्यकता पूरी नमूना सेट को ध्यान में रखने के लिए कहती है। इसलिए अगर रंग 1 के लिए कोई सकारात्मक मिलान नहीं मिल पाता है, तो हम बिल्कुल कोई मैच नहीं मानते हैं और नमूना सेट से रंग 2 और 3 पर विचार नहीं करते हैं।

हालांकि, हम रंग 1 के लिए एक सकारात्मक परिणाम पाते हैं, मान लीजिए कि 80,177,206 जो सिर्फ 1 अंकों लाल चैनल 80 बनाम 81 में बंद हो, तो हम प्रसंस्करण रंग 2 जारी है, और ऐसा हम एक सकारात्मक मैच पाते हैं उसके लिए हम रंग 3 और इतने पर प्रक्रिया करते हैं।

इस समस्या के लिए सबसे उपयुक्त एल्गोरिदम के लिए आपके सुझाव क्या हैं? मुझे ऐसा कुछ चाहिए जो ज्ञात सेट को बिना किसी प्रदर्शन हिट के बहुत बड़े पैमाने पर स्केल करने की अनुमति देगा। स्कैन पर ज्ञात सेट में शायद 1 एम + नमूने होंगे।

मैंने हैशटेबल्स का उपयोग करने के बारे में सोचा, ज्ञात सेट बनाने के लिए प्रति रंग एक। तो मैं रंग 1 पर एक मैच के लिए परीक्षण कर सकता हूं, और यदि पाया जाता है, तो रंग 2 के लिए हैशटेबल का परीक्षण करें, और जब मुझे कोई और हिट नहीं मिलती है तो रोकें। अगर मुझे सकारात्मक हिट के साथ सभी 3 रंग/हैशटेबल्स मिलते हैं, तो मेरे पास एक सकारात्मक सकारात्मक मैच होगा, अन्यथा मैं नहीं करूँगा। हालांकि, यह दृष्टिकोण प्रत्येक रंग के लिए प्रत्येक आरजीबी चैनलों में आवश्यक भिन्नता की अनुमति नहीं देता है। हैशटेबल को सभी को पकड़ने के लिए अनुमति देने के लिए बहुत सारे संयोजन होंगे।

अग्रिम धन्यवाद और इसे दूर पढ़ने के लिए धन्यवाद!

Answer 1

अंत में, SQL और GPU प्रोग्रामिंग (Cudafy) के साथ प्रयोग करने के बाद, सबसे तेज, सबसे आसान, और सबसे डीबग्रेबल समाधान समानांतर का उपयोग कर डेटा के माध्यम से बस फिर से शुरू करना था।()। इस दृष्टिकोण ने 18 एमएमएस में 1.5 एम नमूने संसाधित (90 एम कुल बाइट) उत्पन्न किए।

Answer 2

एक क्रमबद्ध सूची रखें। इसे स्थिर समय के साथ तीन बार सॉर्ट करें, पहले बी द्वारा, फिर जी द्वारा, फिर आर द्वारा। यह इसे आरजीबी ऑर्डर में क्रमबद्ध करता है। अपने इनपुट को देखते हुए, बाइनरी खोज के साथ पहली और अंतिम स्वीकार्य आर के लिए इंडेक्स खोजें।फिर स्वीकार्य जी के लिए उस सीमा को खोजें, फिर बी के लिए फिर से कम सीमा खोजें। पूरी बात ओ (एलजीएन) होना चाहिए।

- जब तक मुझे कुछ याद नहीं आ रहा है, तो यह समाधान 3 रंगों, या 10 रंगों या के रंगों के सेट से मेल खाने के लिए सामान्यीकृत होता है। अपनी रंगीन सेटों की सूची में इंडेक्स की एक सरणी उत्पन्न करें। तैयार करने के लिए, उपरोक्त के रूप में सूचकांक 3 * के समय स्थिर करें। खोजने के लिए, विपरीत क्रम में 3 * के बाइनरी खोज करें।

(यह मानता है कि रंग कॉलम में तय किए गए हैं। यदि वे नहीं हैं, तो भी आप इस विधि का उपयोग कर सकते हैं, लेकिन आपकी अनुक्रमणिका सूची एन * के आकार में जाती है: इसे ए 1, ए 2, ए 3 के लिए एक प्रविष्टि की आवश्यकता होती है। अंत में एक चेक जोड़ें जिसमें आपने प्रत्येक कॉलम से मिलान किया है।)

Answer 3

प्रश्न में आपके विवरण और टिप्पणियों में वार्तालाप के आधार पर, एक साधारण संग्रहीत प्रक्रिया और उपयोगकर्ता परिभाषित प्रकार का उपयोग क्यों न करें? उचित अनुक्रमण के साथ कोई प्रदर्शन समस्या नहीं होनी चाहिए। रंग सेट आप तुलना करना चाहते शामिल मान लिया जाये कि 3 रंग के एकाधिक सेट, मैं शायद कुछ इस तरह करना होगा:

CREATE TABLE KnownColorSets (
    KC_1_R tinyint NOT NULL, 
    KC_1_G tinyint NOT NULL, 
    KC_1_B tinyint NOT NULL, 
    KC_2_R tinyint NOT NULL, 
    KC_2_G tinyint NOT NULL, 
    KC_2_B tinyint NOT NULL, 
    KC_3_R tinyint NOT NULL, 
    KC_3_G tinyint NOT NULL, 
    KC_3_B tinyint NOT NULL 
) 

CREATE TYPE CompareColorSet As TABLE 
(
    CC_1_R tinyint NOT NULL, 
    CC_1_G tinyint NOT NULL, 
    CC_1_B tinyint NOT NULL, 
    CC_2_R tinyint NOT NULL, 
    CC_2_G tinyint NOT NULL, 
    CC_2_B tinyint NOT NULL, 
    CC_3_R tinyint NOT NULL, 
    CC_3_G tinyint NOT NULL, 
    CC_3_B tinyint NOT NULL 
) 



CREATE PROCEDURE stpCompareColorSets 
(
    @Exists bit output, 
    @CompareColorSet dbo.CompareColorSet readonly 
) 
AS 
    DECLARE @MaxDiviation tinyint = 3 -- This may be taken from a General params table or added as a parameter to the stored procedure 
    SET @Exists = 0 
    IF EXISTS (
    SELECT 1 
    FROM KnownColorSets KC INNER JOIN 
    @CompareColorSet CC ON(
     KC_1_R BETWEEN CC_1_R - @MaxDiviation AND CC_1_R - @MaxDiviation 
     AND KC_1_G BETWEEN CC_1_G - @MaxDiviation AND CC_1_G - @MaxDiviation 
     AND KC_1_B BETWEEN CC_1_B - @MaxDiviation AND CC_1_B - @MaxDiviation 

     AND KC_2_R BETWEEN CC_2_R - @MaxDiviation AND CC_2_R - @MaxDiviation 
     AND KC_2_G BETWEEN CC_2_G - @MaxDiviation AND CC_2_G - @MaxDiviation 
     AND KC_2_B BETWEEN CC_2_B - @MaxDiviation AND CC_2_B - @MaxDiviation 

     AND KC_3_R BETWEEN CC_3_R - @MaxDiviation AND CC_3_R - @MaxDiviation 
     AND KC_3_G BETWEEN CC_3_G - @MaxDiviation AND CC_3_G - @MaxDiviation 
     AND KC_3_B BETWEEN CC_3_B - @MaxDiviation AND CC_3_B - @MaxDiviation 
    ) 
) 
    SET @Exists = 1