Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 65
Текст из файла (страница 65)
е. областям с приблизительно постоянным уровнем полутонов), а ориентация пространственной частоты соответствует ориентации края на изображении. алк ТЕОРЕМА ОТСЧЕТОВ В предыдущей главе мы оставили без ответа вопрос о том, насколько точно следует квантовать изображение, чтобы сохранить всю содержащуюся в нем информацию.
Рассмотрим теперь основной теоретический результат, относящийся к этому вопросу, а именно знаменитую теорему отсчетов Шеннона '). Основная идея теоремы отсчетов заключается в установлении соответствия между резкими изменениями интенсивности на изображении и высокими пространственными частотами в его спектре, Если спектр изображения не содержит высоких частот, то само изображение не содержит резких перепадов уровня полутонов, и поэтому можно предположить, что такое изображение не следует квантовать слишком точно.
В соответствии с этим мы будем называть функцию интенсивности д(х, у) ограниченной по полосе частот, если ее спектр Фурье О()„, гв) равен нулю во всех точках, где )Ц нли )Ц больше, чем некоторая величина Ф'. Теорема отсчетов Шеннона утверждает, что ограниченная по полосе частот функция может быть точно восстановлена по отсчетам изображения, взятым на ненулевом расстоянии друг от друга, а также показывает, как должно выполняться восстановление.
Математические детали теоремы отсчетов станут несколько ясней, если мы ограничим наше внимание одномерным случаем. В случае одномерной функции интенсивности ') формулы прямого и обратного преобразований Фурье (1) и (2) принимают более простой вид: ь) В отечественной лнтервтуре зте теореме называется теоремой Котельникове. Онв была сформулирована В. А. Котельниковым в 1933 г. звдолго до по. явлення рзбог Шеннона.
Обобщение теоремы отсчетов для функций двух переменных было дано Н, К. Игнзтьевым в 1953 г. — Прим. перез, е) Квк н раньше, мы можем предположить, что одномерная функция ннтенснвностн представляет собой знзчення двумерной функции вдоль разреза в плоскости изображения. Гн, 8. Ананиз пространственная частот 324 д(х) =Т '(6()„)» = = ~ 6((„)ехр(2пг(„х)а(„. О (4) Одномерная функция интенсивности и (х) ограничена по полосе час- тот, если ее спектр Фурье 6 (Г„) равен нулю во всех точках, где (Ц больше, чем некоторая величина (оо, называемая шириной лсокххя частот.
Ряс. 8.2. Фунхцяя я!пс. Для того чтобы упростить формулировку' теоремы отсчетов, нам необходимо сначала ввести одно дополнительное определение. Поскольку при доказательстве теоремы появляются функции вида з1п(пи)'пи, определим новую функцию, обозначив ее з1пс: я!п (пи) зйпс и = — „' График этой функции показан на рис. 8.2. Предположим теперь, что нам дана (одномерная) функция интенсивности д и ее спектр Фурье 6 ограничен по ширине полосы частот величиной (о". Разложим функцию 6Д„) в ряд Фурье на интервале — И'<~„(%'. И 6(г'„) =,5 с ехр 1 — 2п(~„(~~,)1, где коэффициенты разложения с„определяются формулой 2%' ) 6(гн)ехр ~2пг~" (2ю)1а Спектр 6 тождественно равен нулю вне его полосы частот, поэтому в формуле обратного преобразования (4) мы можем заменить бес- л.х.
теорема отоетав конечные пределы на ~В'. Следовательно, интеграл в формуле (6) представляет собой точный результат д (х) обратного преобразова- ния, вычисленный в точках х=т/2%7. Поэтому выражение (6) при- нимает вид (7) Подставляя (7) в (5), получаем Ю ~(Р„)=2у,х'~ к (2В)ехр ~ — 2пЕ/„(2В)~ при — (('"(/ (((", (8) 6(/„) =0 в остальных случаях. й'(х) = ~~' ° й (~~ ) з(пс ~2(Г' (х — ~~ )~ .
а=- а (9) Выражение (9) и есть результат теоремы отсчетов Шеннона. На словах оно означает, что функцию я можно воспроизвести, расположив набор функций з(пс через интервалы 1/2ЯГ вдоль оси Х, введя масштабирование умножением каждой функции з1пс на величину отсчета д, взятого в ее центральной точке, н сложив все масштабированные функции з(пс. Чем больше ширина полосы частот Г, тем меньше должен быть отсчетный интервал !/2((Г.
Смысл этого утверждения очевиден: ббльшая полоса частот означает, что функция интенсивности может изменяться быстрей, и поэтому отсчеты должны располагаться чаще стем, чтобы уловить все эти изменения. Другой теоретический результат, подтверждающий такую интерпретацию, известен как неравенство Бернштейна, Это неравенство, которое мы приводим без доказательства, можно сформулировать следующим образом. Предположим, что функция интенсивности не только ограничена по полосе частот, но и не превышает по.
модулю некоторой величины М. Тогда ее производная не превышает по модулю 2пВ'М. Выразим ту же мысль с помощью формул: если для функции я ширина полосы частот равна 1р' и (х(х)1(М для всех к, то (д' (х)1(2п Я~М. Поскольку любое физически существующее изображение имеет ограниченную интенсивность, из неравенства Уже из формулы (8) можно видеть, что функция интенсивности д полностью определяется отсчетами, взятыми на конечном расстоянии друг от друга, поскольку ее спектр зависит только от величин д, взятых с интервалом 1/2%Г.
Окончательный вывод теоремы отсчетов может быть получен применением. обратного преобразования Фурье к выражению (8). Это нетрудно, поскольку для этого необходимо лишь проинтегрировать экспоненциальную функцию в пределах от — Я7 до ЯГ. Пропуская подробности, выпишем результат: Гл. 8. Анализ нространствснннх частот Бернштейна следует, что максимальная скорость изменения функции интенсивности пропорциональна ширине ее полосы частот. Для двумерных функций интенсивности положение полностью аналогично только что исследованному одномерному случаю как в математическом плане, так и с точки зрения качественного анализа, Двумерную функцию интенсивности можно полностью определить ее отсчетами, взятыми в узлах квадратной сетки с интервалом 1/2(Р.
Незначительное усложнение связано с тем обстоятельством, что эта функция может иметь различную ширину полосы частот в направлении осей /„н /и, т. е. спектр б(/„, /о)=0, когда либо 1/,~~ > Яг„, либо Ц) (й„. Если такой случай имеет место, мы можем брать отсчеты в узлах прямоугольной, а не квадратной сетки с интервалами 1/2йр„и 1/2%'и в направлении осей Х и )' соответственно.
При этом небольшом обобщении двумерный аналог формулы (9) выглядит следующим образом: н н й(х У)= л~!л Е У (звт 21Р ) м га=-сю н=-н х з(пс ~211Рз(х — й~ — )~ з(пс ~2%'„(у — ~~, )~ . (10) 8.3. СРАВНЕНИЕ С ЭТАЛОНОМ И ТЕОРЕМА О СВЕРТКЕ Мы уже писали в предыдущей главе о том, что сравнение с эталоном во всем многообразии своих форм представляет собой одну из фундаментальных операций анализа изображений. Теперь мы хотели бы установить связь между одной из форм сравнения с эталоном и преобразованием Фурье. Для наших целей удобней считать, что сравнение с эталоном выполняется с помощью вычисления функции взаимной корреляции. Ее определение в дискретной форме было дано в выражении (5) гл. 7, но существует такое же определение и для аналоговых функций.
Пусть даны аналоговая функция интенсивности д(х, у) и аналоговый эталон 1(х, У). Тогда их Здесь снова имеется сумма (произведений) функций япс, причем каждое слагаемое помножено на масштабный коэффициент, равный величине соответствующего отсчета исходной функции интенсивности. Итак, теорема отсчетов представляет для нас интерес с двух дополняющих друг друга точек зрения. С точки зрения практики она показывает, насколько точно нужно квантовать функцию интенсивности, чтобы сохранить всю первоначальную информацию. С точки зрения качественного анализа она дает дополнительное понимание смысла высоких пространственных частот.
8.8. Сравнение с эталоном и теорема о сверпте 327 функция взаимной корреляции йэ~с(х, у) определяется формулой ') Йвс(х, у) =~~К(и, ~)1(и — х, Р— у)с(иФ. (11) В силу определенных причин„которые пока не очевидны, будем называть сверткос) уп( двух функций интенсивности у и 1 следующую величину: Ф ки((х, у) =- ))у(и, ())1(х — а, у — ()) с(ис()1. (12) Операция свертки коммутативиа и может интерпретироваться следующим образом: функция 1 переносится в заданную точку (х, у) и затем переворачивается относительно перенесенных осей координат. Далее вычисляется взаимная корреляция между перевернутой функцией 1 и исходной функцией интенсивности д.
В соответствии с этим, если эталон описывается функцией 1(х, у), его перевернутый вариант 1(х, у) определяется формулой 1(х, у) =1( — х, — у). Ясно, что сгиК(х, у) =Яке(х, у), (13) поскольку ') В формуле (7.5) пределы суммирования выбирались такими, чтобы аргументы функции Г попадали в область перемещенного эталона.
Здесь для наших целей удобней испольэовать бесконечные пределы и считать, что эталонная функция равна нулю эа пределами основной области. йг и 1 (х, у) = ~ ~ у (а, р) 1 (х — а, у — р) с(и с(р = = ) ~ д (а, р) Г (сс — х, р — у) с(и сср =- Ф =й (х, у). Таким образом, свертка, по существу, эквивалентна корреляции, Мы увидим в скором времени из теоремы о свертке, что свертка эквивалентна также перемножению спектров.
Следовательно, у нас появится возможность вычисления взаимной корреляции путем перемножения. Чтобы упростить доказательство теоремы о свертке, рассмотрим предварительно более простое утверждение, называемое обычно теоремой о сдвиге. Те о р ем а о сд в и ге. Если чг'(д(х, у))=сг(Г„, )и), то К (у(х — сс, у — р)) =ехр ( — 2пс (р„и+1эр)1 6(1*,)п). Гл. 8. Анализ проопронппвонннх ноаноа 328 До к а з а т е л ь с т в о. Записав определение спектра и подставив величины х'=х — а и у'=у — (з, получим 7[у(х — а, у — р)) = Ф =) ~ у(х — а, у — [)) ехр [ — 2п(((„х+[„у)) е(хс(у= = )) у(х',у') ехр [ — 2п(((„(х'+а)+(о(у'+р))) дх'ду' = З =ехр [ — 2п((1„а+ (нр)) б ((„, („), что доказывает теорему.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
