{"entities":{"Q1183400":{"pageid":1194149,"ns":120,"title":"Item:Q1183400","lastrevid":66442680,"modified":"2026-04-12T10:06:15Z","type":"item","id":"Q1183400","labels":{"en":{"language":"en","value":"A remark on NP-completeness of picture matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33266"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$73AA6590-174C-4CAD-B2D3-F68B717CB2E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"582328a8e7bd7ec70a4d3af09397a69fed1c487f","datavalue":{"value":{"text":"A remark on NP-completeness of picture matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183400$4366A06F-B86B-44BF-8BDD-B24A68B247E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9dc2e9aac28cdc57e58ea70278f0cae8063b046","datavalue":{"value":"0749.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$E208FBEB-0731-4A71-9D44-A290B1F704A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cf2d65198229abf3d621b6fa48abaac9dc84cf7e","datavalue":{"value":"10.1016/0020-0190(91)90022-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$9C95C42A-30EB-4F7A-BFF4-8BD02CBB332C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8937b4624bc5c4b9632fa0ade7a7162a269014b5","datavalue":{"value":{"entity-type":"item","numeric-id":1183398,"id":"Q1183398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$88F37EB4-8391-4A42-AA06-D74CE9F36EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"83de6675e5073ee0c48e7317f8ba4916503c1b93","datavalue":{"value":{"entity-type":"item","numeric-id":557808,"id":"Q557808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$95F66774-0460-40ED-859D-7EE13EAC8345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74c550ab94fb7828f8da57fd741391361e86827b","datavalue":{"value":{"entity-type":"item","numeric-id":1183399,"id":"Q1183399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$2BE44AE8-2C4C-43F7-97CC-E65F0C5B40C2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$B6590437-C88D-46BE-BEEC-5F266A86039D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183400$C72DA520-84D0-462C-B7F3-CC4288DCE3B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"542e9fde91d9df0d3b41b4ef0f87e4b4be7a0bde","datavalue":{"value":"One of the most relevant features in the design of advanced image data- base systems is the retrieval of pictures using the spatial relations among the objects contained in the pictures to be retrieved \\textit{N. S. Chang} and {K. S. Fu} [Query-by-pictorial-example, IEEE Trans. Software Eng. 6, 519-524 (1980)], \\textit{S. -K. Chang} and \\textit{S. -H. Liu} [IEEE Trans. Pattern Anal. and Mach. Intell. 6, No. 4, 475-484 (1984; Zbl 0542.68077)].   Corresponding to different levels of strictness in checking for spatial constraints, three types of picture matching are defined in \\textit{S. -K. Chang} and \\textit{S. -H. Liu} [loc. cit]. We prove the NP-completeness of the two less strict types of matching.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183400$F01355C8-56BE-4BD5-9D4E-504D7F51A16D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$D645A010-8A4B-4094-8300-17054DEC06C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$564DBEF7-9184-4BAF-B10F-FD16A0AA4E8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$47D90694-B2D3-47FA-A680-FD2A97F56033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ab7a0d2add14e0dbd91ec8ae1d32a5bb94f2fb34","datavalue":{"value":"68U10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$F043FD90-856C-4DA2-8FE9-67087F89662D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd6bd83891f27c19bee113f7c165269d845507ce","datavalue":{"value":"33266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183400$E2F8DB15-CA03-4F0B-A4A2-10C8DCC654E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3604872cd1c96e6c8dde657fdf1aa052bd30f77","datavalue":{"value":"information retrieval","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183400$49A072A7-AEC0-476D-BF0D-DDC4EFBB9E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"950c6fe2fd196d0d731a47e3dbeceea94d096933","datavalue":{"value":"image databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183400$9697F84C-FA87-4442-802B-FCD9908A9918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df553fce9b7871a5f1b7ccf801d45a0d41a61c7e","datavalue":{"value":"picture matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183400$0CA84F7D-B294-451F-B239-2311C19B504D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$842FFAA6-EC8A-4D22-B661-ADB37FA7BF95","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad14e0ac5825ff680da69abc67e34f5c7204cc52","datavalue":{"value":{"entity-type":"item","numeric-id":3330554,"id":"Q3330554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$FF5D533E-D8F6-482F-BE56-FDC12747A298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183400$DF79F463-9BD9-479F-B25C-8EA54C0F1A8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f53e5733c7b1884eb13ad9ccfbd3ca1ee77d480","datavalue":{"value":{"entity-type":"item","numeric-id":2493523,"id":"Q2493523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fd5b2ad2b49b45420d34913483ef7e7cfec95d0","datavalue":{"value":{"amount":"+0.8603604435920715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183400$3FE6EB96-D3B6-4A21-A4C1-07F21B2A7D5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaf9ee4111884079167de97027b7e17fc79a201b","datavalue":{"value":{"entity-type":"item","numeric-id":294810,"id":"Q294810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d28d230e1351ca231f6480e61a22aef9aebcafc","datavalue":{"value":{"amount":"+0.8078609704971313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183400$B7E5F1C2-CA04-46A5-979D-026780D3A994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98de1a30b8904060b677561a66852d0ce156d5a6","datavalue":{"value":{"entity-type":"item","numeric-id":4421052,"id":"Q4421052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcf81b2ed3eb5dc05137589421774843b064a56a","datavalue":{"value":{"amount":"+0.7905363440513611","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183400$7E8B0EA3-1391-408E-B3B1-F6522AA05766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe6571317fdfcc2c4243720a83a2642db47d8ad8","datavalue":{"value":{"entity-type":"item","numeric-id":2508684,"id":"Q2508684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7d923a450c6238257a395cd115b75cd37196cb3","datavalue":{"value":{"amount":"+0.7556586265563965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183400$1CC3F08D-B865-4B4D-B0D5-5EA2C0930285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd216df8735f71acac9a0adf0098609e4df1df37","datavalue":{"value":{"entity-type":"item","numeric-id":2493527,"id":"Q2493527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f3a3b45f551791076efc8897cce23ff1eca550a","datavalue":{"value":{"amount":"+0.7538301944732666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183400$0C386C97-16E5-47C6-98FA-9294F1064CD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A remark on NP-completeness of picture matching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_remark_on_NP-completeness_of_picture_matching"}}}}}