Statistiska åtgärder som kommer från informationsteorin representerar intressanta grunder för bild- och videobehandlingsuppgifter såsom bildsökning och videoobjektspårning. Låt oss till exempel nämna entropin och Kullback-Leibler-divergensen. Noggrann uppskattning av dessa åtgärder kräver att man anpassar sig till den lokala provtätheten, särskilt om uppgifterna är högdimensionella. K närmaste granne (kNN) ramverk har använts för att definiera effektiva variable-bandwidth kärnbaserade estimatorer med en sådan lokalt adaptiv egenskap. Tyvärr, dessa estimatorer är beräkningsintensiva eftersom de förlitar sig på att söka grannar bland stora uppsättningar av d-dimensionella vektorer. Denna beräkningsbörda kan minskas genom förhandsstrukturering av data, t.ex. Använda binära träd som föreslagits av biblioteket Ungefärlig närmaste granne (ANN). Men den senaste öppningen av Graphics Processing Units (GPU) till allmänna beräkningar med hjälp av NVIDIA CUDA API erbjuder bilden och video bearbetning gemenskapen en kraftfull plattform med parallella beräkningsmöjligheter. I detta dokument föreslår vi en CUDA implementering av "brute force" kNN sökning och vi jämför dess prestanda med flera CPU-baserade implementationer inklusive en likvärdig brute force algoritm och ANN. Vi visar en hastighetsökning på syntetiska och verkliga data med upp till en eller två storleksordningar beroende på data, med ett kvasilinjärt beteende med avseende på datastorleken i ett givet, praktiskt intervall.
I dokumentet REF jämförs GPU-implementationen av brute force k-NN med flera CPU-baserade implementationer och genomförandet av algoritmer från ANN 1 bibliotek (Ett bibliotek för ungefärlig närmaste grannsökning).
Fast k nearest neighbor search using GPU
{'venue': '2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops', 'journal': '2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops', 'mag_field_of_study': ['Computer Science']}