Эффект «согласованного голосования» и возможности его использования

Суть эффекта заключается в следующем. Пусть имеется датчик, измеряющий какой-то физический параметр, причём большинство показаний датчика случайны, и только небольшая часть правильна. Если значение измеряемого параметра постоянно, то при определенных условиях можно выявить эти правильные показания, даже если их число ничтожно по сравнению с общим числом измерений. Для этого нужно так организовать получение и анализ гистограммы показаний, чтобы в позиции верного измерения образовался яркий экстремум. Назовём это эффектом «согласованного голосования».

Как пример, может быть рассмотрена следующая ситуация. Изображения участка поверхности Земли, полученные в разное время и трансформированные в единую систему координат, могут оказаться немного сдвинутыми друг относительно друга (на несколько или на первые десятки пикселей). Если изображения отличаются не существенно, то можно перебрать все возможные варианты сдвига и определить при каком сдвиге сходство (например, корреляция) изображений максимально. Однако этот способ применить во многих случаях нельзя, так как суммарная площадь изменённых участков (изменение объектов, сезонные изменения, облака, дефекты съёмки и пр.) может оказаться больше сохранившихся участков, положение которых неизвестно.

Можно было бы определить сдвиг даже по небольшому фрагменту этих изображений. Однако, неизвестно, по какому именно фрагменту можно найти реальный сдвиг, а для какого фрагмента нет соответствия, и результатом поиска будет ложное, случайное значение. Абсолютное значение оценки сходства при поиске сдвига также не могло быть достаточным критерием надёжности измерения так как сходство может быть не абсолютным, а только в целом, с различием деталей. В итоге, нет возможности определить сдвиг изображений по какому-то одному фрагменту. Средний вектор сдвига, найденный по нескольким фрагментам, также не даёт достоверную оценку, так как большинство фрагментов может дать вектор, не связанный с искомым сдвигом.

Эффект «согласованного голосования» позволил построить следующую процедуру.

Небольшой фрагмент одного изображения сравнивался с соответствующей областью второго изображения. Находился и фиксировался «лучший» сдвиг фрагмента, при котором сходство оказывалось максимальным. Лучший сдвиг определялся для большого числа фрагментов, равномерно покрывающих изображение, и строилась гистограмма лучших сдвигов. Оказалось, что даже при изменении большей части изображения, по пику в гистограмме можно было найти правильный сдвиг и оценить надёжность полученного результата.

Обобщим этот подход, и рассмотрим, на что следует обращать внимание, чтобы надёжно воспользоваться эффектом «согласованного голосования». Формальное описание поможет точнее описать ситуацию и позволит распространить этот метод на более широкий круг практических задач.

Сформулируем в общем виде проблему, которую постараемся решить, используя эффект согласованного голосования. Пусть в многомерном евклидовом пространстве X = {x} заданы функции {Fi(x)}. Область определения функции обозначим D(Fi) ⊆ X. На множестве этих функций заданы аффинное преобразование Y и мера сходства S.
Преобразование Y осуществляется с учётом числовых параметров {p}, Y(Fi, p1, p2, …, pk) = Fj. Для каждого pi задано ni значений, а значит, имеется N = n1×n2×…×nk наборов этих параметров (векторов) P = (p1, p2, …, pk), причём существует такой «нулевой» вектор, при котором функция Fi преобразуется в себя. Отметим, что при преобразовании Y возможно изменение D(Fi).

Мера S даёт числовую оценку сходства S(Fi, Fj) = Hij в интервале [0,1], где 1 означает, что Fi и Fj идентичны, а 0 означает, что сходства нет или нет возможности осуществить сравнение. Сходство определяется по области Dij = D(Fi) ∩ D(Fj) или в подобласти d ⊂ Dij. В последнем случае будем говорить о локальном сходстве. Сходство равна 0 в том случае, если область его измерения пуста или недостаточна (последнее определяется свойствами меры).

Рассматривается следующая задача. Для пары функций Fi и Fv нужно найти вектор параметров P, который обеспечивает их максимальное сходство, S(Y(Fi, P), Fv) = Hiv. Такой вектор можно было бы найти перебором. Однако есть два обстоятельства, осложняющих поиск. Первое. Нас будет интересовать ситуация, когда в области Dij функции Fi и Fv не сходны, Hiv << 1, но возможно есть неизвестная нам «область сходства» A⊂Dij, для которой существует вектор Pa, обеспечивающий высокое сходство функций. Второе. Даже в этой области, A, сходство функций не абсолютно, и нет заранее определенного порогового значения сходства, на которое можно было бы опереться.

Решить поставленную задачу, когда одновременно неизвестны и область сходства, и порог сходства, и нужные параметры преобразования (и даже существуют ли они) не удалось. Однако для таких мер S, в которых высокое сходства в области D возможно только тогда, когда высоко и локальное сходство в подобластях B ⊂ D (например, корреляция), можно сформулировать задачу несколько иначе. Чтобы найти вектор Pa будем искать не A, а его небольшие подобласти B ⊂ A, рассчитывая на то, что должно быть много областей B, в которых высокое сходство обеспечивает один и тот же вектор Pa.

Предлагается следующий алгоритм. Покроем D(Fi) набором связных областей Wm ⊂ X, Wm ∩ D(Fi) ≠ Ø, где m = 1, 2, …, M, которые будем называть фрагментами, например, множество гиперкубов. Для каждого Wm найдём вектор Pm, который максимизирует сходство, рассчитанное по этому фрагменту, и будем говорить, что фрагмент Wm «проголосовал» за вектор Pm. Строим многомерную гистограмму, которая аккумулирует «голоса» всех фрагментов Wm. Ожидаемый эффект «согласованного голосования» основан на том, что для всех Wm ⊂ A максимум сходства будет найден при одном и том же векторе параметров, обозначим его Pu. А для остальных Wm будут найдены разнообразные, случайные значения Pm распределённые практически равномерно. В этих условиях в позиции гистограммы голосов Pu можно ожидать яркий пик.

Если найден яркий уникальный пик гистограммы, то он указывает на вектор Pu, который обеспечивает сходство функций, а область сходства «очерчивается», хотя и довольно грубо, объединением фрагментов «голосовавших» за Pu. Если такой пик не обнаружен, то либо нет области сходства, либо неудачно организован поиск. Отметим, что предложенный алгоритм опирается не на абсолютное значение сходства, а на его относительные, максимальные значения. Решение, принимаемое по наличию яркого пика, выглядит более надёжным, чем решение по превышению порога сходства. Тому, что означает «яркий уникальный пик», как его искать, как создать условия его порождения — посвящён следующий раздел.

Обратим внимание, что решения нет и в том случае, если в гистограмме присутствует несколько пиков близкой величины. Это может произойти из-за того, что распределение случайных голосов не равномерно, имеет свой пик. Другая ситуация. У пары функций может оказаться несколько областей сходства с разными параметрами преобразования. В этом случае будет найдена область, которая существенно больше остальных. «Голоса» от меньших областей либо потеряются в фоне, либо не дадут принять решение.

Представляется вполне реальным обобщить предложенный подход на более широкий класс преобразований и пространств. Возможность работы с иными преобразованиями, Y, обусловлена тем, что в операциях алгоритма, никак не использовано то, что это преобразование является аффинным. Что касается перехода к не евклидовым пространствам X, то при этом важно сохранить возможность построения набора фрагментов, которые покрывают область определения D(Fi) «равномерно» (аналогично решётке гиперкубов), чтобы в распределении случайных голосов не образовывались ложные максимумы. Также, возможно, не потребуется и связность фрагментов.

Размерность и размер «гистограммы голосования» определяется возможными вариантами «голосования», то есть размерностью и числом векторов параметров, N. Если значения каждого параметра, pi, получены квантованием диапазона возможных значений, то увеличение диапазона и уменьшение шага квантования резко увеличивает размер гистограммы. Возможно, в каких-то ситуациях окажется допустимым сначала решать задачу при более грубом квантовании, а значит с меньшим числом вариантов, и затем перейти к детальному анализу в меньшем диапазоне. Однако, если квантование слишком грубо, то можно не получить хорошего совпадения функций F, и надёжного экстремума меры сходства, который обеспечивает «согласованное голосование».

Число фрагментов. Для того, чтобы надёжно найти пик «согласованных голосов» в «гистограмме голосования», случайные «голоса» должны создавать достаточно ровный «фон», тогда пик, превышающий этот «фон» в несколько раз, окажется достоверным указателем на нужную позицию. Фон выравнивается, если гистограмма «населена», т.е. в её «ячейках» не мало голосов (скажем, около 10). Это можно обеспечить соответствующим соотношением между числом отсчётов гистограммы N, и числом голосов. Если голосуют все M фрагментов и случайные голоса распределены равномерно (обсудим это ниже), а достаточное среднее число голосов в каждой ячейки обозначим h, то M должно быть не меньше N×h. Точнее было бы потребовать, чтобы на столько большим было M – V, где V — число согласованных голосов. Однако, при организации поиска число V ещё неизвестно, так что будим исходить из того, что данный метод поиска нужен, когдаV относительно мало, скажем V/M < 0,2. Если же в конкретной ситуации окажется, что V существенно больше, чем 0,2M, то населённость фона гистограммы будет небольшой, но зато пик, скорее всего, окажется в разы больше, чем флуктуации неровного фона.

Необходимо упомянуть ситуацию, с которой на практике не встречались. Если N мало (мало параметров и известен узкий диапазон их возможных значений), то среднее число случайных голосов, h, может оказаться большим, и небольшое число согласованных голосов, V, может не сформировать относительно большого пика гистограммы. В этой ситуации стоит посмотреть, нельзя ли увеличить число возможных значений параметров, сделав меньше шаг квантования и увеличив диапазон значений параметров, даже зная, что это избыточно, что нужных значений там нет. При этом случайные голоса распределятся среди большего числа возможных вариантов голосования, h уменьшится, а V сохранится.

За счёт согласованного голосования мы хотим получить достаточно большой пик, т.е. V/h > T, где T — порог, или ориентировочно, V > T·N/M. Таким образом, если требуется обеспечить выбор из большого числа возможных параметров, N, то необходимо организовать голосование большого числа фрагментов, M. Тут мы подходим к следующему принципиальному выбору — размер фрагментов.

Размер фрагментов и их организация. С одной стороны, для того, чтобы голосовало большое число фрагментов, нужно покрыть D(Fi) фрагментами небольшого размера. Причём фрагменты должны быть небольшими и по сравнению с возможными размерами области A (условно — с её «шириной»).

С другой стороны, важно учитывать, что внутри слишком маленького фрагмента, у сравниваемых функций может не оказаться достаточных изменений, деталей, «рисунка». Другими словами, в пределах фрагмента у функций может оказаться «нечего» сравнивать, и оценка сходства будет не информативна. Что именно считать слишком маленьким фрагментом, зависит от свойств функций и меры S, как мы отметим в примере ниже.

Есть возможность увеличить число голосующих фрагментов, не уменьшая их размер, а добавив ещё одно покрытие D(Fi) фрагментами того же размера. Допустимо, чтобы фрагменты из первого и второго набора пересекались, но важно, чтобы фрагменты покрывали D(Fi) равномерно, не создавая участков «более насыщенных фрагментами», чем остальные. В частности, это может быть решётка гиперкубов, существенно смещённая относительно первой решётки. Можно и дальше добавлять фрагменты покрытия, учитывая указанные требования.

Распределение «случайных голосов». Обнаружить ничтожное число верных решений возможно, если распределение остальных, не имеет собственных ярких экстремумов. Поэтому необходимо отследить и отфильтровать те экстремумы гистограммы, которые являются артефактами конкретной реализации предложенного метода. Один из возможных источников ложных экстремумов - организация процедуры сравнения при поиске вектора параметров, дающего максимальное сходство. Перебор параметров может происходить по фиксированной последовательности P1, P2, … Сначала в качестве максимального фиксируется сходство фрагмента Wm с функцией Fv при параметрах P1, а затем этот выбор меняется на Pk, если при этих параметрах оценка сходства будет строго больше. Предположим, что сходство при всех параметрах одинаково, тогда максимальное сходство окажется у первого в последовательности вектора. Таким образом, в силу детерминированности процесса выбора, у первого (или у последнего) в последовательности перебора вектора параметров искусственно увеличивается вероятность быть выбранным.

Организуя процесс построения гистограммы, необходимо внимательно анализировать все его шаги, чтобы не возникали такие «искусственные» пики.

Поиск пиков в гистограмме. Необходимо обнаружить позицию гистограммы, в которой число голосов в разы превышает среднее число голосов. Причём и по абсолютной величине это число голосов должно быть достаточно велико, чтобы не оказаться случайным. Кроме того, величина пика отражает размер «области сходства», а очень маленькие области (и пики) могут и не интересовать.

Чтобы избавиться от описанных выше пиков, которые связаны с порядком перебора параметров, можно поступить следующим образом. Увеличим диапазон значений каждого признака на две позиции — одно значение на шаг квантования меньше нижней границы и одно значение на шаг больше верхней. Крайние позиции будут аккумулировать пики, порождённые порядком перебора, а мы не будем учитывать эти позиции при анализе гистограммы.

В некоторых случаях, например, если шаг квантования параметров слишком велик, может образоваться не один оптимальный вектор параметров, а несколько векторов с «соседними» значениями параметров. В результате, «голоса» фрагментов распределятся между соседними ячейками гистограммы, создавая «широкий» пик. Абсолютное значение гистограммы в «широком» пике окажется существенно меньше, и вместо одного окажется несколько высоких значений в соседних ячейках гистограммы.

Предполагая такую возможность, имеет смысл анализировать не только отдельные ячейки, но и группы соседних ячеек с тем, чтобы обнаруживать и такой «широкий» пик.

Надёжность результата. Если в гистограмме голосов обнаружен яркий пик, то необходимо провести проверку — единственный ли это пик. Если существуют и другие пики, близкие по величине, то нет уверенности в правильном выборе. Поэтому найдём следующий по величине пик и отбракуем полученный результат, если величина второго пика несущественно меньше первого.

Если пик не найден, то результат можно проверить, поменяв порядок в паре сравниваемых функций и повторив процедуру. Это имеет смысл в силу того, что процедура сравнения несимметрична. Кроме того, возможно, слишком узок диапазон параметров и его стоит увеличить. Можно также изменить набор фрагментов. Если пик найден не надёжно, то можно произвести преобразование с найденными параметрами Fj = Y(Fi, Pu), и повторить поиск уже для пары Fj, Fv.

Итак, мы рассмотрели, на что необходимо обратить внимание, чтобы создать условия для согласованного голосования. В первую очередь — это число векторов параметров, число и размер фрагментов, и устранение «привилегированных» векторов.

В заключение рассмотрим возможности развития предложенного полхода. Исходя из приведённого формального описания, можно легко обобщить этот метод на другие ситуации. Во-первых, сопоставляя изображения, можно допускать их отличие не только по расположению (сдвиг), но и по повороту, масштабу. Практически допустимый диапазон поиска этих параметров зависит от размера и качества изображений, так как требуется соответствующее увеличение размера гистограммы и экспоненциальный роста числа «голосующих» фрагментов.

Во-вторых, можно работать не с двумерными функциями, как изображение, а с функциями иных размерностей. При этом изменяется только способ сравнения функций, задания фрагментов и получения «голосов», а работа с гистограммой остаётся прежней. Представляется возможным получать эффект «согласованного голосования» и при не равномерном распределении случайных «голосов», если в этом распределении нет большого пика, конкурирующего с «согласованными голосами».

Наконец, не исследована упомянутая выше возможность обобщить метода на более широкий класс преобразований и пространств, с которыми пока не экспериментировали.