PHP - Наистина бърз начин за откриване на бяло пространство около изображение?

Имам нужда от наистина бърз метод за откриване на бяло пространство около изображение, по-специално имам нужда от координатите на мястото, където започва първият небял пиксел за всяка страна (напр. отляво, отгоре, отдясно, отдолу.)

ImageMagick е твърде бавен, така че преминава през всеки пиксел от всяка страна с GD и вижда дали е бял. Трябва да направя около 500 000 000 изображения, така че всяка микросекунда има значение.

Между другото изображението е само черно-бяло.

Ако има външно приложение, което може да направи това, което мога exec с PHP, тогава това би било добре.


php gd
person Alasdair    schedule 26.03.2012    source източник
comment
Дали бялата рамка е хубава еднаква граница около картината? Дали бялото е наистина бяло или само много ярко?   -  person KillerX    schedule 26.03.2012
comment
Не, изобщо не е еднакво... може да е всичко и различно от всяка страна. Изображението може дори да е изцяло бяло.   -  person Alasdair    schedule 26.03.2012
comment
Така че предполагам, че имате нужда от този, който се откроява най-много от всяка страна? PS: Най-вероятно ще получите по-висока скорост на обработка, извършвайки действителната обработка на C или C++.   -  person KillerX    schedule 26.03.2012
comment
500m изображения - уф! Би трябвало да се радвам да знам вашия случай на употреба!   -  person halfer    schedule 26.03.2012
comment
Това звучи като работа за паралелизиране. Ако трябваше да го предоставите на куп сървъри - или дори мрежа от настолни компютри - ще го направите много по-бързо. Въпреки това, опитвали ли сте imagemagick от SSD или RAM устройство?   -  person halfer    schedule 26.03.2012
comment
Можете ли да ни дадете по-подробно описание как изглеждат снимките? Имам предвид алгоритъм, но не съм сигурен дали би бил приложим. Това, което ме интересува, са често срещаните форми на вашите снимки. Предимно правоъгълни форми, завъртяни/леко деформирани? Предимно кръгъл? Напълно непредвидими (като X, E, T...)?   -  person KillerX    schedule 26.03.2012
comment
@halfer: Раздава се на куп сървъри и да, всеки използва RAM устройство за временно съхранение.   -  person Alasdair    schedule 26.03.2012
comment
@KillerX: текст, рисунка, снимки и др.   -  person Alasdair    schedule 26.03.2012
comment
Колко сървъра получавате в група? ;)   -  person halfer    schedule 26.03.2012
comment
Не виждам как PHP е подходящ работен кон за това. Ако имате толкова много изображения, трябва да използвате роден език и да използвате всеки трик за ефективност, който можете да си представите за всеки конкретен файлов формат.   -  person Gleno    schedule 26.03.2012
comment
@Gleno, не е много подходящо, но това е, което използвам. C++ би бил много по-добър, Assemby по-добър от това, а специално ядро ​​на ОС, което да прави само това, което искам, би било още по-добро, но PHP е това, с което работя за практически цели. Както и да е, PHP обединява само това, което се прави най-вече от различни други приложения, написани на C или C++ - просто така се случва, че PHP се използва за тази част.   -  person Alasdair    schedule 26.03.2012

Отговори (2)


arrow_upward
3
arrow_downward

има ли някаква допълнителна информация, която знаете за изображенията, която може да се използва за помощ?

Например изображенията започват бели, след това стават черни и след това остават черни? или всеки пиксел може да е бял или черен и фактът, че някой е бял или черен, не ви говори нищо за другите?

Ако всеки пиксел може да бъде бял или черен, независимо от другите пиксели, тогава не виждам как можете да направите много по-добре от това да проверявате всеки пиксел в цикъл, докато не намерите първия, който не е бял...

Ако знаете, че ако петият пиксел отляво е бял, тогава 0-4 определено също са бели, тогава може да сте в състояние да проверите по-малко пиксели вместо това, като използвате някакъв вид модифицирано двоично търсене (тъй като можете да пропуснете проверката 0-4 в този случай и просто маркирайте 5, след това 10 и ако 5 е бяло и 10 е черно, знаете, че точката е някъде между 5-10, така че можете да разделите разликата и да проверите 7 и т.н. и т.н., докато намерите точката, в която те се променят.)

Мисля, че тук може да се стигне до компромис между скорост и точност. Най-точният начин е да разрежете всяка колона и ред, като започнете от краищата, като проверите всеки пиксел. След като намерите удар в колона, вие сте намерили ръба от едната страна. Това може да се направи паралелно, тъй като всяка проверка е независима. може да успеете да ускорите това, като, както казахте, проверявате само всеки n-ти пиксел, но е вероятно това да се изрязва от време на време, особено с толкова голям набор от данни. това може или не може да бъде приемливо. може да успеете да подобрите това, като проверите около областта, в която намерите съвпадение, за да проверите дали съвпадението е точно. Така че, ако проверите всеки 3-ти пиксел и намерите попадение в пиксел 15, проверете 14, за да видите дали е попадение (и 13, ако 14 е). като използвате това, може да успеете да се измъкнете с по-малко проверки.

person Sam Holder    schedule 26.03.2012
comment
Черните пиксели обикновено са на блокове естествено, така че мога да се измъкна с пропускане на всеки следващ пиксел или дори да проверя само 1 от 3. Освен това може да е текст, рисунка или разсеяна снимка върху изображението. - person Alasdair; 26.03.2012

arrow_upward
1
arrow_downward

Един алгоритъм, който може да работи, ако имате предимно непрекъсната граница от по-тъмни пиксели: Лява страна:

  1. Вземете средния пиксел и започнете да проверявате пикселите вдясно, докато намерите черен.
  2. След това се придвижете от там нагоре/надолу, докато стигнете до черен пиксел
  3. Когато намерите черен пиксел, преместете се наляво, докато ударите бял
  4. Повторете 2,3, докато не стигнете отгоре/отдолу

Това, разбира се, няма да работи, ако има пропуски, като в текста.

person KillerX    schedule 26.03.2012
comment
Работата е там... може да има голямо бяло пространство в средата на изображението, само с черни пиксели около ъглите. - person Alasdair; 26.03.2012
comment
Теоретично бихте могли да започнете от да кажем 10% от върха и да отидете надясно до 50% от ширината. Ако не уцелите нищо, преместете един ред нагоре и следващия преместете 2 реда надолу и т.н... Най-вероятно ще трябва да покриете по-малко пиксели, отколкото да сканирате ред по ред/колона по колона. - person KillerX; 26.03.2012