Имам изискване, което изисква съпоставяне на примерен набор от цветови стойности срещу известен набор от стойности, за да намеря или точно съвпадение, или съвпадения, които са на приемливо разстояние. Не съм напълно сигурен кой алгоритъм би бил най-подходящ за това и търся предложения.
Мислех да използвам SQL заявка, тъй като смятам, че това би било лесен подход, но в идеалния случай това ще бъде направено в паметта на сървъра на приложения или дори на GPU за максимална скорост.
Пример:
Да кажем, че ни е даден набор от три RGB цветови стойности, две сини и една оранжева:
Примерен комплект:
Цвят 1: 81 177 206 (син)
Цвят 2: 36, 70, 224 (син)
Цвят 3: 255, 132, 0 (оранжев)
Този набор от 3 цветови стойности трябва да бъде съпоставен с много по-голям набор от цветови стойности, за да се види дали този набор съществува в него, или със същите точни RGB стойности за всеки от 3-те цвята - или - ако съществува някакъв модел, където RGB стойност на цветовете варира в приемлива степен. Да приемем, че всеки от RGB компонентите може да бъде с до 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]
Ако образец F съществуваше с тези стойности в известния набор, щяхме да получим положително попадение, защото това са точните RGB стойности като цвят 1 в нашия примерен набор. Освен това трябва да приемем различна степен на разлики в RGB стойностите, така че следното също ще върне положителни резултати, тъй като всяка RGB стойност е в рамките на 3 цифри от стойностите на цвят 1 от примерния набор:
Положителни попадения: (не забравяйте, че цвят 1 е: 81,177,206)
Пример F: 80,177,206 (червеният канал е на 1 цифра разстояние)
Проба F: 81,175,204(зелени и сини канали на 2 цифри разстояние)
Пример F: 82,179,208 (и трите канала в рамките на 3 цифри)
Ако обаче разстоянието е твърде голямо, тогава съвпадение няма да бъде намерено. Всеки RGB компонент трябва да бъде в рамките на 3 цифри, за да задейства положителен резултат. Така че, ако проба F изглеждаше по следния начин, ние няма да получим положителен резултат, защото разстоянието е твърде голямо:
Отрицателни попадения:
Пример F: 85,177,206 (червеният канал е на 4 цифри разстояние)
Проба F: 81,170206 (зеленият канал е на 7 цифри разстояние)
Пример F: 81,177,200 (синият канал е на 6 цифри разстояние)
Досега сме взели предвид Цвят 1 от Примерния комплект. Изискването обаче изисква да се вземе предвид целият набор от проби. Така че, ако не могат да бъдат намерени положителни съвпадения за Цвят 1, тогава приемаме, че изобщо няма съвпадение и не вземаме предвид Цветове 2 и 3 от Примерния набор.
Въпреки това, ако намерим положителен резултат за Цвят 1, да кажем 80,177,206, което е само 1 цифра по-малко в червения канал 80 срещу 81, тогава правим да продължим да обработваме Цвят 2 и ако намерим положителен мач за това, след което обработваме Цвят 3 и т.н.
Какви са вашите предложения за най-подходящ алгоритъм за този проблем? Имам нужда от нещо, което ще позволи на известния набор да се разраства в много големи размери без прекалено голям удар в производителността. Вероятно ще има 1M+ проби в известния набор в мащаб.
Мислех да използвам хеш-таблици, по една на цвят, за да конструирам известния набор. Така че мога да тествам за съвпадение на цвят 1 и ако го намеря, да тествам хеш-таблицата за цвят 2 и да спра, когато не намеря повече попадения. Ако премина през всичките 3 цвята/хеш-таблици с положителни попадения, тогава ще имам общо положително съвпадение, иначе не бих. Този подход обаче не позволява необходимата вариация във всеки от RGB каналите за всеки цвят. Ще има твърде много комбинации, за да се даде възможност за конструиране на хеш-таблици, които да поберат всичко.
Благодаря предварително и благодаря, че прочетохте дотук!
