Advances in Pattern Recognition Stan Z. Li # Markov Random Field Modeling in Image Analysis Third Edition Stan Z. Li Center for Biometrics and Security Research & National Laboratory of Pattern Recognition Institute of Automation Chinese Academy of Science Beijing 100190, China Stan.ZQ.Li@gmail.com Series editor Professor Sameer Singh, PhD Research School of Informatics, Loughborough University, Loughborough, UK ISBN: 978-1-84800-278-4 e-ISBN: 978-1-84800-279-1 DOI: 10.1007/978-1-84800-279-1 Advances in Pattern Recognition Series ISSN 1617-7916 British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2008943235 © Springer-Verlag London Limited 2009 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Printed on acid-free paper Springer Science+Business Media springer.com In Memory of My Mother “An excellent book — very thorough and very clearly written.” — Stuart Geman “I have found the book to be a very valuable reference. I am very impressed by both the breadth and depth of the coverage. This must have been a truly monumental undertaking.” — Charles A. Bouman # Foreword by Anil K. Jain The objective of mathematical modeling in image processing and computer vision is to capture the intrinsic character of the image in a few parameters so as to understand the nature of the phenomena generating the image. Models are also useful to specify natural constraints and general assumptions about the physical world; such constraints and assumptions are necessary to solve the "inverse" problem of three-dimensional scene interpretation given two-dimensionalAdvances in Pattern Recognition Stan Z. Li # Markov Random Field Modeling in Image Analysis Third Edition Stan Z. Li Center for Biometrics and Security Research & National Laboratory of Pattern Recognition Institute of Automation Chinese Academy of Science Beijing 100190, China Stan.ZQ.Li@gmail.com Series editor Professor Sameer Singh, PhD Research School of Informatics, Loughborough University, Loughborough, UK ISBN: 978-1-84800-278-4 e-ISBN: 978-1-84800-279-1 DOI: 10.1007/978-1-84800-279-1 Advances in Pattern Recognition Series ISSN 1617-7916 British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2008943235 © Springer-Verlag London Limited 2009 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Printed on acid-free paper Springer Science+Business Media springer.com In Memory of My Mother “An excellent book — very thorough and very clearly written.” — Stuart Geman “I have found the book to be a very valuable reference. I am very impressed by both the breadth and depth of the coverage. This must have been a truly monumental undertaking.” — Charles A. Bouman # Foreword by Anil K. Jain The objective of mathematical modeling in image processing and computer vision is to capture the intrinsic character of the image in a few parameters so as to understand the nature of the phenomena generating the image. Models are also useful to specify natural constraints and general assumptions about the physical world; such constraints and assumptions are necessary to solve the "inverse" problem of three-dimensional scene interpretation given two-dimensional